给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

格式

输入

第一行 :一个整数n 第二行：n个整数 第三行：目标值target

输出

目标值target的下标

样例1

6
-1 0 3 5 9 12
9

4

样例2

6
-1 0 3 5 9 12
2

-1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。