← 返回题目列表

AtCoder · abc350_c

F. 排序

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

分数: 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