题目描述

:::epigraph[Stanley P. Y. Fung. Is this the simplest (and most surprising) sorting algorithm ever? arXiv:2110.01111] 我们给出了一个极其简单的排序算法。它看上去显然是错的，但我们证明了它事实上是对的。 :::

在学习了 2021 国际大学生程序设计竞赛亚洲区域赛南京站的《Paimon Sorting》一题中奇怪的排序算法后，小青鱼想到了如下的一个问题。

给定序列 $a_1, a_2, \cdots, a_n$ 表示一个 $n$ 的排列，您需要将该排列按升序排序，为此可以执行以下操作至多 $\lfloor \frac{n}{2} \rfloor$ 次：选择两个下标 $l$ 和 $r$ 满足 $1 \le l < r \le n$ 以及 $a_l > a_r$，将 $a_l, a_{l + 1}, \cdots, a_r$ 按升序进行排序。

请回忆：一个 $n$ 的排列是一个长度为 $n$ 的序列，每个从 $1$ 到 $n$（含两端）的整数在其中都恰好出现一次。另外，$\lfloor x \rfloor$ 表示小于等于 $x$ 的最大的整数。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 100$）表示排列的长度。

第二行输入 $n$ 个不同的整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le n$）表示给定的排列。

保证所有数据 $n$ 之和不超过 $10^4$。

输出格式

对于每组数据，首先输出一行一个整数 $k$（$0 \le k \le \lfloor \frac{n}{2} \rfloor$）表示您执行的操作次数。接下来输出 $k$ 行，其中第 $i$ 行输出两个由单个空格分隔的整数 $l_i$ 和 $r_i$，表示您为第 $i$ 次操作选择的两个下标。

可以证明答案总是存在。如果有多种合法答案，您可以输出任意一种。

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

提示

对于第一组样例数据，在第 $1$ 次操作后排列变为 $\{2, 3, 1, 4, 5, 6\}$，在第 $2$ 次操作后排列变为 $\{1, 2, 3, 4, 5, 6\}$，此时排列是升序的。