P16316 [ICPC 2023 Jinan R] Strange Sorting

:::epigraph[Stanley P. Y. Fung. Is this the simplest (and most surprising) sorting algorithm ever? arXiv:2110.01111] We present an extremely simple sorting algorithm. It looks obviously wrong, but we prove that it is actually correct. ::: After learning about the strange sorting algorithm in the problem "Paimon Sorting" from ICPC 2021 Asia Regional Nanjing Site, Xiaoqingyu came up with the following question. Given a sequence $a_1, a_2, \cdots, a_n$, which is a permutation of size $n$, you need to sort it in non-decreasing order. To do this, you may perform the following operation at most $\left\lfloor \frac{n}{2} \right\rfloor$ times: choose two indices $l$ and $r$ such that $1 \le l < r \le n$ and $a_l > a_r$, then sort $a_l, a_{l + 1}, \cdots, a_r$ in non-decreasing order. Recall that a permutation of size $n$ is a sequence of length $n$ in which each integer from $1$ to $n$ (inclusive) appears exactly once. Also, $\lfloor x \rfloor$ denotes the greatest integer not larger than $x$.

There are multiple test cases. The first line contains an integer $T$, the number of test cases. For each test case: The first line contains an integer $n$ ($1 \le n \le 100$), the length of the permutation. The second line contains $n$ distinct integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), representing the given permutation. It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.

For each test case, first output one line with an integer $k$ ($0 \le k \le \left\lfloor \frac{n}{2} \right\rfloor$), the number of operations you perform. Then output $k$ lines, where the $i$-th line contains two integers $l_i$ and $r_i$ separated by a single space, indicating the two indices you choose for the $i$-th operation. It can be proven that an answer always exists. If there are multiple valid answers, you may output any one of them.

For the first sample, after the first operation the permutation becomes $\{2, 3, 1, 4, 5, 6\}$, and after the second operation it becomes $\{1, 2, 3, 4, 5, 6\}$. At this time, the permutation is in non-decreasing order. Translated by ChatGPT 5