说明

一天晚上，我们在家里看电视，某大型娱乐节目在玩猜数游戏。主持人在女嘉宾的手心上写一个10以内的整数，让女嘉宾的老公猜是多少，而女嘉宾只能提示大了，还是小了，并且只有3次机会。 主持人悄悄地在美女手心写了一个8。 老公：“2。” 老婆：“小了。” 老公：“3。” 老婆：“小了。” 老公：“10。” 老婆：“晕了!” 孩子说：“天啊，怎么还有这么笨的人。”那么，聪明的孩子，现在随机写1～n范围内的整数，你有没有办法以最快的速度猜出来呢？

给定n个元素，这些元素是有序的（假定为升序），从中查找特定元素x。

输入格式

第一行是一个整型数m(m<100)表示共有m组测试数据。

每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据有n个数。

第2行，有n个整数$s_i(0<s_i<10000)$。

最后一行，待查找的数x。

输出格式

先对输入数据进行非递减排序，然后再折半查找。

对于每一组输入，输出x所在的位置（最小为1），如果不存在输出-1。

每组的输出占一行。

样例

3
11
60 17 39 15 8 34 30 45 5 52 25
17
5
8 3 48 6 12
10
8
56 7 5 48 16 25 43 39
48

4
-1
7

来源

《趣学算法》3.2节