分数: 300 点
问题陈述
给你一个排列 A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
变换 A 进入 (1,2,\ldots,N) 通过在之间执行以下操作 0 和 N-1 次,包括:
- 操作:选择任意一对整数 (i,j) 这样 1\leq i < j \leq N。交换位于的元素 i-th 和 j- 第一个位置 A.
可以证明,在给定的约束条件下,总是可以变换 A 进入 (1,2,\ldots,N).
约束
- 2 \leq N \leq 2\times 10^5
- (A_1,\ldots,A_N) 是一个排列 (1,2,\ldots,N).
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 \ldots A_N
输出
让 K 是操作次数。打印 K+1 行。
第一行应包含 K.
的 (l+1)- 第行 (1\leq l \leq K) 应包含整数 i 和 j 选择为 l第一个操作,以空格分隔。
任何满足问题陈述中的条件的输出都将被视为正确。
示例输入 1
5 3 4 1 2 5
示例输出 1
2 1 3 2 4
操作更改顺序如下:
- 最初, A=(3,4,1,2,5).
- 第一个操作交换第一个和第三个元素,使得 A=(1,4,3,2,5).
- 第二个操作交换第二个和第四个元素,使得 A=(1,2,3,4,5).
如下所示的其他输出也被认为是正确的:
4 2 3 3 4 1 2 2 3
示例输入 2
4 1 2 3 4
示例输出 2
0
示例输入 3
3 3 1 2
示例输出 3
2 1 2 2 3