题目描述

请在一个有序递增数组中（不存在相同元素）查找值 $x$ 的位置。如果 $x$ 在数组中不存在，请输出 $-1$。

数组下标从 $1$ 开始。

输入格式

第一行包含一个整数 $n$，表示数组元素个数。

第二行包含 $n$ 个整数，表示数组中的 $n$ 个递增元素，整数之间用空格分隔。

第三行包含一个整数 $x$，表示要查找的数。

输出格式

输出一个整数，表示 $x$ 在数组中的位置；如果不存在，输出 $-1$。

样例

10
1 3 5 7 9 11 13 15 17 19

2

数据范围与提示

• $1 \le n \le 10^6$
• $1 \le$ 数组元素值 $\le 10^8$
• $0 \le x \le 10^8$

来源

二分 分治