← 返回题目列表

Codeforces · 1375/E

E. 反转交换排序

中文机器翻译题面 查看原题

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,...,a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — 数组的元素。

输出

如果不存在这样的列表,则打印 -1。否则,在第一行中,您应该打印一个整数 $$$m$$$ ($$$0 \le m \le \dfrac{n(n-1)}{2}$$$) — 列表中的对数。

以下 $$$m$$$ 行中的第 $$$i$$$ 行应包含两个整数 $$$u_i, v_i$$$ ($$$1 \le u_i < v_i\le n$$$)。

如果有多个可能的答案,您可能会找到其中任何一个。

示例

输入 #1

3
3 1 2

输出 #1

2
1 3
1 2

输入 #2

4
1 8 1 6

输出 #2

2
2 4
2 3

输入 #3

5
1 1 1 2 2

输出 #3

0

注意

在第一个示例测试用例中,数组将按 $$$[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]$$$。

在第三个示例测试用例中,数组已经排序。