题目描述

小杨正在学习计算机科学中的经典算法，今天他的目标是实现一个高效的二分查找算法。小杨知道二分查找是一种在有序数组中查找特定元素的高效算法，其时间复杂度为 O(logn)，非常适合处理大规模数据。

小杨的数组是严格递增的，且不包含重复元素。他需要找到给定值 x 在数组中的位置。如果 x 存在于数组中，他需要输出其位置（索引从1开始计数）；如果不在数组中，则输出-1。

小杨希望通过实现这个算法来提高自己的编程技能，并解决老师布置的作业。

输入格式

第一行，一个整数n，代表数组元素个数（$n <= 10^6$）

第二行，n个数，代表数组的n个递增元素（1<=数组元素值<=2*$10^8$）

第三行，一个整数x，代表要查找的数（0<=x<=2*$10^8$）

注意取值范围都在int 范围内

输出格式

x在数组中的位置，或者-1。

10
1 3 5 7 9 11 13 15 17 19
3

2