给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

格式

输入

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

输出

target若存在，输出target下标，否则输出target按顺序插入的位置

样例1

4
1 3 5 6 
5

2

样例2

4
1 3 5 6
2

1

样例3

4
1 3 5 6
7

4

提示:

• 1 <= nums.length <= 10<sup>4</sup>
• -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
• nums 为 无重复元素 ​的 升序 ​排列数组
• -10<sup>4</sup> <= target <= 10<sup>4</sup>