Binary Search
Contest: Codeforces Round 935 (Div. 3)
Difficulty rating: 1700
Tags: binary search, constructive algorithms, greedy

Anton got bored during the hike and wanted to solve something. He asked Kirill if he had any new problems, and of course, Kirill had one.

You are given a permutation $$$p$$$ of size $$$n$$$, and a number $$$x$$$ that needs to be found. A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

You decided that you are a cool programmer, so you will use an advanced algorithm for the search — binary search. However, you forgot that for binary search, the array must be sorted.

You did not give up and decided to apply this algorithm anyway, and in order to get the correct answer, you can perform the following operation no more than $$$2$$$ times before running the algorithm: choose the indices $$$i$$$, $$$j$$$ ($$$1\le i, j \le n$$$) and swap the elements at positions $$$i$$$ and $$$j$$$.

After that, the binary search is performed. At the beginning of the algorithm, two variables $$$l = 1$$$ and $$$r = n + 1$$$ are declared. Then the following loop is executed:

1. If $$$r - l = 1$$$, end the loop
2. $$$m = \lfloor \frac{r + l}{2} \rfloor$$$
3. If $$$p_m \le x$$$, assign $$$l = m$$$, otherwise $$$r = m$$$.

The goal is to rearrange the numbers in the permutation before the algorithm so that after the algorithm is executed, $$$p_l$$$ is equal to $$$x$$$. It can be shown that $$$2$$$ operations are always sufficient.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le x \le n \le 2\cdot 10^5$$$) — the length of the permutation and the number to be found.

The second line contains the permutation $$$p$$$ separated by spaces ($$$1 \le p_i \le n$$$).

It is guaranteed that the sum of the values of $$$n$$$ for all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output an integer $$$k$$$ ($$$0 \le k \le 2$$$) on the first line — the number of operations performed by you. In the next $$$k$$$ lines, output $$$2$$$ integers $$$i$$$, $$$j$$$ ($$$1 \le i, j \le n$$$) separated by a space, indicating that you are swapping the elements at positions $$$i$$$ and $$$j$$$.

Note that you do not need to minimize the number of operations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
0
1
3 4
2
2 4
1 5
2
4 5
2 4
1
1 3

Editorial:
In fact, the problem can be solved in a single operation.
Let's start a binary search on the initial permutation. We will get some index $$$l$$$. Then, it is enough to swap $$$p_l$$$ and $$$x$$$. Now our binary search will stop exactly at the number $$$x$$$. Notice that in the search, any number less than or equal to $$$x$$$ affects the result like $$$x$$$. Indeed, $$$p_l \le x$$$ remains true if we replace $$$p_l$$$ with $$$x$$$.
Note that if we swapped two numbers that give the same result in the condition of the binary search, then the final $$$l$$$ will not change.
The previous statements assumed that $$$p_l \le x$$$. Indeed, in the algorithm description, after changing $$$l$$$, the number $$$p_l$$$ cannot become greater than $$$x$$$. It is also necessary to consider the case when $$$l = 1$$$ after executing the algorithm. If $$$l = 1$$$, then at each iteration of the algorithm, $$$p_m > x$$$, in particular, this means that $$$p_m$$$ was never equal to $$$x$$$. In this case, swapping $$$p_1$$$ and $$$x$$$ will also not affect the result ($$$l$$$) of the binary search.
Complexity: $$$\mathcal{O}(n)$$$.