Permutations and Queries

A permutation $P=[P_1,P_2,\cdots,P_N]$ of length $N$ is given.

In one reversal, choose two integers $l,r$ satisfying both conditions below.

• $1 \leq l \leq r \leq N$.
• $r-l+1 \geq \left\lceil\cfrac{N}{2}\right\rceil-1$.

Then reverse the order of the contiguous segment $P_l,P_{l+1},\cdots,P_r$.

Sort $P$ in increasing order using at most $3N$ reversals, and print the reversals you used.

The input is given from Standard Input in the following format:

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

Each case is given in the following format:

$N$ $P_1\ P_2\ \cdots\ P_N$

For each test case, print the number $Q$ of reversals on the first line.

Then print $Q$ lines. On the $i$-th line, print the two integers $l_i,r_i$ chosen for the $i$-th reversal.

The output must satisfy all conditions below.

• $0 \leq Q \leq 3N$.
• $1 \leq l_i \leq r_i \leq N$ ($1 \leq i \leq Q$).
• $r_i-l_i+1 \geq \left\lceil\cfrac{N}{2}\right\rceil-1$ ($1 \leq i \leq Q$).
• After applying every printed reversal in order, the permutation must be $[1,2,\cdots,N]$.

If there are multiple solutions, print any of them.

• $1 \leq T \leq 100$.
• $2 \leq N \leq 2\,000$.
• $P$ is a permutation of $1,2,\cdots,N$.
• The sum of $N$ over all test cases does not exceed $2\,000$.