Start 2023-11-08 00:00:00

20231111分治算法

End 2023-11-17 00:00:00
Contest is over.
Now 2024-05-18 16:44:49

A. 折半查找法

Description

在一排(10 000以内)已按编号从小到大排好序的数中,快速地查找到某个数所在的位置。

Input

第1行是整数N,表示有N个数,第2行是N个数,第3行为整数M,表示要查找的数。

Output

输出一个数,即如找到该数,则输出位置,否则输出-1。

Examples

Input

3
2 4 6
4

Output

2

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit