CF1375E Inversion SwapSort

Madeline 有一个长度为 $n$ 的整数数组 $a$。如果一对整数 $(u, v)$ 满足以下条件，则称其在 $a$ 中形成一个逆序对： - $1 \le u < v \le n$。 - $a_u > a_v$。 Madeline 最近发现了一张神奇的纸，可以让她写下两个下标 $u$ 和 $v$，并交换 $a_u$ 和 $a_v$ 的值。感到无聊的她决定写下一个满足以下条件的下标对列表 $(u_i, v_i)$： - 列表中的所有对都是不同的，并且在 $a$ 中形成逆序对。 - $a$ 中所有形成逆序对的下标对都在列表中。 - 从给定数组出发，依次按列表顺序交换 $u_1$ 和 $v_1$ 处的值，再交换 $u_2$ 和 $v_2$ 处的值，依此类推，最终数组 $a$ 会变为非递减有序。 请构造这样一个列表，或者判断不存在这样的列表。如果有多种答案，输出任意一种即可。

输入的第一行包含一个整数 $n$（$1 \le n \le 1000$），表示数组的长度。 下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组的元素。

如果不存在这样的列表，输出 $-1$。否则，第一行输出一个整数 $m$（$0 \le m \le \dfrac{n(n-1)}{2}$），表示列表中的对数。 接下来的 $m$ 行，每行输出两个整数 $u_i, v_i$（$1 \le u_i < v_i \le n$）。 如果有多种答案，输出任意一种即可。

在第一个样例中，数组变化过程为 $[3,1,2] \rightarrow [2,1,3] \rightarrow [1,2,3]$。 在第二个样例中，变化过程为 $[1,8,1,6] \rightarrow [1,6,1,8] \rightarrow [1,1,6,8]$。 在第三个样例中，数组已经是有序的。 由 ChatGPT 4.1 翻译