Start 2023-05-20 00:00:00

2023春季第二次阶段测试赛

End 2023-05-31 00:00:00
Contest is over.
Now 2025-12-01 23:56:28

C. 二分查找

Description

用递归算法实现二分查找,即:有n个已经从小到大排序好的数据(不重复),从键盘输入一个数X,用对半查找方法,判断它是否在这n个数中。

Input

第一行,正整数n,N≤10^5

第二行,n个整数(int范围内,不重复),中间用空格分隔

第三行,整数X。

Output

如果找到X,输出其位置;否则输出-1。

Examples

Input

10
10 20 30 40 50 60 70 80 90 100
90

Output

9

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit