Sort

题目描述

你被给定了一个置换 $A=(A_1,\ldots,A_N)$，它是 $(1,2,\ldots,N)$ 的一个排列。
通过执行以下操作 0 到 $N-1$ 次（含端点），将 $A$ 变换为 $(1,2,\ldots,N)$：

操作：选择任意整数对 $(i,j)$，满足 1\leq i < j \leq N。交换 $A$ 中第 $i$ 个和第 $j$ 个位置的元素。

在给定的约束下，总可以将 $A$ 变换为 $(1,2,\ldots,N)$，这一点可以被证明。

输入格式

输入按下列格式由标准输入给出： $N$ $A_1$ $\ldots$ $A_N$

输出格式

设 $K$ 为操作次数。打印 $K+1$ 行。
第 1 行应包含 $K$。
第 $(l+1)$ 行（$1\leq l \leq K$）应包含第 $l$ 次操作选择的整数 $i$ 和 $j$，两者之间以空格分隔。
满足题目陈述中条件的任意输出都将被视为正确。

5
3 4 1 2 5

2
1 3
2 4

4
2 3
3 4
1 2
2 3

4
1 2 3 4

0

3
3 1 2

2
1 2
2 3

提示

$2 \leq N \leq 2\times 10^5$ $(A_1,\ldots,A_N)$ 是 $(1,2,\ldots,N)$ 的一个置换。 所有输入值都是整数。操作将序列按如下方式改变：

初始时，$A=(3,4,1,2,5)$。 第一次操作交换第 1 个和第 3 个元素，使得 $A=(1,4,3,2,5)$。 第二次操作交换第 2 个和第 4 个元素，使得 $A=(1,2,3,4,5)$。

其他输出例如下列也被视为正确：

标签: AtCoder|abc350C

来源

AtCoder|abc350C