103502: [Atcoder]ABC350 C - Sort

Problem Statement

You are given a permutation $A=(A_1,\ldots,A_N)$ of $(1,2,\ldots,N)$.
Transform $A$ into $(1,2,\ldots,N)$ by performing the following operation between $0$ and $N-1$ times, inclusive:

• Operation: Choose any pair of integers $(i,j)$ such that $1\leq i < j \leq N$. Swap the elements at the $i$-th and $j$-th positions of $A$.

It can be proved that under the given constraints, it is always possible to transform $A$ into $(1,2,\ldots,N)$.

Constraints

• $2 \leq N \leq 2\times 10^5$
• $(A_1,\ldots,A_N)$ is a permutation of $(1,2,\ldots,N)$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $\ldots$ $A_N$

Output

Let $K$ be the number of operations. Print $K+1$ lines.
The first line should contain $K$.
The $(l+1)$-th line ($1\leq l \leq K$) should contain the integers $i$ and $j$ chosen for the $l$-th operation, separated by a space.
Any output that satisfies the conditions in the problem statement will be considered correct.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

• Initially, $A=(3,4,1,2,5)$.
• The first operation swaps the first and third elements, making $A=(1,4,3,2,5)$.
• The second operation swaps the second and fourth elements, making $A=(1,2,3,4,5)$.

Other outputs such as the following are also considered correct:

4
2 3
3 4
1 2
2 3

Sample Input 2

4
1 2 3 4

Sample Output 2

0

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3

问题描述

给你一个排列 $A=(A_1,\ldots,A_N)$，它是$(1,2,\ldots,N)$的全排列。
通过执行以下操作0到$N-1$次（包括0和$N-1$次），将$A$转换为$(1,2,\ldots,N)$：

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

可以证明，在给定的约束条件下，总是可以将$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$）应包含第$l$次操作选择的整数$i$和$j$，用空格分隔。
满足题目描述中条件的任何输出都将被视为正确。

样例输入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