我们知道这样一个游戏：给出一个范围中的某个数字，在有限次内猜中这个数字。如1-10之间选择一个数x，每次可以猜一个数，并且得知猜的结果大于、小于、等于x，在最坏的情况下最少用几次机会能猜中它呢？技巧是先猜5，如果大了猜2或3，如果小了猜7或8……最多猜测4次就可以得到正确答案（虽然最多猜3次之后答案已经确定下来了）。

在有序数组中（非升或非降序列）查找是否存在特定值经常使用的二分查找（折半查找）的道理与之类似，以在含n个元素的不降序列arr中查找k为例：取要查找下标范围的中间值mid，若arr[mid]大于要查找的数，则下次查找的下标范围变为从0到mid-1，若arr[mid]小于要查找的数，则下次查找的下标范围变为mid+1到n。循环这样的过程，当arr[mid]==k时说明k存在于数组中；当查找范围变得不合理（范围的最小值大于最大值——参考mid-1和mid+1仔细理解此处），说明k不存在于arr中。

但事情并没有这么简单，现在请你找到一个非降序列中，与k最接近的元素。

第一行，一个正整数n，表示数组长度。

接下来n行，每行一个整数，表示数组的元素。（数组元素已经按生序排列）。

接下来一行，一个正整数k，表示要查找的值。

对于100%的数据：

1\le n \le 1\cdot 10^5 ；

0\le 数组元素,k \le 1\cdot 10^9 ；

一行，一个整数，表示数组中最近接近k的值。如果有多个，则输出较小的一个。

计算mid的表达式：

错误写法：mid=(right+left)/2; //可能溢出

正确写法：mid=left+(right-left)/2;