安东在徒步旅行中感到无聊,想要解决一些问题。他问基里尔是否有任何新问题,当然,基里尔有一个。
给你一个大小为$$$n$$$的排列$$$p$$$,以及需要找到的数字$$$x$$$。长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
您认为自己是一名很酷的程序员,因此您将使用高级算法进行搜索 - 二分搜索。但是,您忘记了对于二分查找,数组必须是排序的。
你并没有放弃,决定应用这个算法,为了得到正确的答案,你可以在运行算法之前执行以下操作不超过$$$2$$$次:选择索引$$$i$$$、$$$j$$$ ($$$1\le i, j \le n$$$)并交换$$$i$$$和$$$j$$$位置的元素。
之后,执行二分查找。在算法开始时,声明了两个变量 $$$l = 1$$$ 和 $$$r = n + 1$$$。然后执行以下循环:
1. 如果$$$r - l = 1$$$,则结束循环
2. $$$m = \lfloor \frac{r + l}{2} \rfloor$$$
3. 如果$$$p_m \le x$$$,则赋值$$$l = m$$$,否则$$$r = m$$$。
目标是在算法之前重新排列排列中的数字,以便在执行算法之后,$$$p_l$$$ 等于$$$x$$$。可以证明 $$$2$$$ 操作总是足够的。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$) — 测试用例的数量。然后按照测试用例的描述进行操作。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le x \le n \le 2\cdot 10^5$$$) — 排列的长度和要找到的数字。
第二行包含由空格分隔的排列 $$$p$$$ ($$$1 \le p_i \le n$$$)。
保证所有测试用例的$$$n$$$值的总和不超过$$$2\cdot 10^5$$$。
输出
对于每个测试用例,在第一行输出一个整数 $$$k$$$ ($$$0 \le k \le 2$$$) — 您执行的操作数。在接下来的 $$$k$$$ 行中,输出 $$$2$$$ 整数 $$$i$$$, $$$j$$$ ($$$1 \le i, j \le n$$$),并用空格分隔,表示要交换位置 $$$i$$$ 和 $$$j$$$ 处的元素。
请注意,您不需要最小化操作次数。
示例
输入 #1
5 6 3 1 2 3 4 5 6 6 5 3 1 6 5 2 4 5 1 3 5 4 2 1 6 3 4 3 1 5 2 6 3 2 3 2 1
输出 #1
0 1 3 4 2 2 4 1 5 2 4 5 2 4 1 1 3