题目描述

有个长度为n的数组a，元素各不相同，按照递增顺序排列。我们想要知道整数x是否在数组a中。由于数组实在太大，用穷举的方法会浪费很多时间。

输入格式

第一行一个整数n(1≤n≤10^5)表示数组的长度；

第二行n个整数ai(1≤ai≤10^3)；

第三行一个整数x(1≤x≤10^3)。

输出格式

如果可以在a中找到x，输出这个数的位置（位置从1开始），否则输出-1。

输入/输出样例

10
1 2 3 5 7 8 9 10 12 15
5

4

说明/提示

时间1000ms，内存256MiB