思路

• 关键等价：若在某次操作中选择的位置的值分别为 $v$ 与 $v+1$，则操作后它们交换位置；否则不可能保持为排列。 证明要点：多重集计数平衡要求对 $a\to a+1$ 与 $b\to b-1$ 的四个计数改变量相互抵消，只有当 $b=a+1$ 时成立。

• 因而，允许的操作等价于“交换值为相邻数对 $(v, v+1)$ 的两个位置”，这就是在“值空间”的相邻换位。

• 设 $\text{pos}[v]$ 为值 $v$ 的当前位置，则当且仅当 $\text{pos}[v] > \text{pos}[v+1]$ 时，$(v, v+1)$ 构成一对“逆序”。每次交换 $(v, v+1)$ 会恰好使逆序数减少 $1$。

• 令

  $\text{inv}(p)$=$\left|{(i,j)\mid 1\le i<j\le n,\ p_i>p_j}\right|$

题目内容

给定长度为 $n$ 的排列 {$p_1,p_2,…,p_n$}，定义一次操作为：

选择两个不同的位置 $i,j$ ，将 $p_i$ 增加 $1$ ，同时将 $P_j$ 减少 $1$ ;同时需要保证每次操作后，数组仍是 $1$ 到 $n$ 的一个排列。

问将数组变为严格递增排列 {$1,2,…,n$} 需要的最少操作次数。

长度为 $n$ 的排列是由 $1,2,...,n$ 这 $n$ 个整数、按任意顺序组成的数组(每个整数均恰好出现一次)。例如，{$2,3,1,5,4$} 是一个长度为 $5$ 的排列，而 {$1,2,2$} 和 {$1,3,4$} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述

第一行输入整数 $n(1≤n≤10^3)$ 表示排列长度；

第二行输入 $n$ 个整数 $p_1,p_2,...,p_n(1≦p_i≦n)$ ，它们构成 $1$ 到 $n$ 的个排列。

输出描述

第一行输出一个整数 $k$ ，表示需要的最少操作次数。

此后 $k$ 行，第 $i$ 行输出两个整数 $x_i,y_i(1≦x_i,y_i≦n;x_i≠y_i)$ ，表示第 $i$ 次操作将 $P_{x_i}$ 増加 $1$ ，$P_{y_i}$ ; 减少 $1$ .

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

3
3 2 1

输出

3
3 2
3 1
2 1

说明

在这个样例中，初始排列为 {$3,2,1$}：

第一次操作 $(x_1= 3,y_1= 2)$ 后排列变为 {$3,1,2$} ；

第二次操作 $(x_2= 3,y_2 = 1)$ 后排列变为 {$2,1,3$} ；

第三次操作 $(x_3= 2,y_3 = 1)$ 后排列变为 {$1,2,3$} ；

综上，通过 $3$ 次操作将排列变为严格递增排列 ${1,2,3}$ 。我们可以证明，这是最少需要的操作次数。

样例2

输入

1
1

输出

0