Background背景

请在一个有序不递减的数组中（数组中有相等的值），采用二分查找，找到值x第1次出现的位置，如果不存在x请输出-1。

Input输入

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

第二行，n个整数，用空格隔开，代表数组的n个元素（1<=数组元素的值<=$10^8$）

第三行，一个整数x，需要查找的数。

Output输出

如果x能找到，输出这个数字第一次出现的位置，如果不能找到，输出-1。

Samples样例

8
1 3 5 5 7 8 8 9
5

3

5
1 2 4 5 6
10

-1

Limitation限制

1s, 1024KiB for each test case.