Problem Description

:::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$.

Input Format

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$.

Output Format

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.

3
6
2 3 4 6 5 1
5
1 2 3 4 5
3
2 3 1

2
3 6
1 3
0
1
1 3

Hint

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