题目描述

给定一个 $(1,2,\ldots,N)$ 的排列 $P=(P_1,P_2,\ldots,P_N)$。

请判断是否可以通过不超过 $2\times 10^3$ 次如下操作将 $P$ 排成升序。如果可以，请给出一种实际的操作方案。

• 选择满足 $1\leq i \leq N-1, 0 \leq j \leq N-2$ 的整数 $i,j$。将 $P$ 中的第 $i$ 项和第 $i+1$ 项 $(P_i, P_{i+1})$ 拿出，剩下的序列记为 $Q=(Q_1,Q_2,\ldots,Q_{N-2})$。然后将 $P$ 替换为 $(Q\_1,\ldots,Q\_j, P\_i, P\_{i+1}, Q\_{j+1},\ldots,Q\_{N-2})$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

如果无法在 $2\times 10^3$ 次操作内将 $P$ 排成升序，输出 No。

如果可以，设操作次数为 $M\ (0 \leq M \leq 2\times 10^3)$，第 $k$ 次操作 $(1\leq k\leq M)$ 选择的 $i,j$ 分别为 $i_k, j_k$，则输出格式如下：

Yes $M$
$i_1$ $j_1$
$i_2$ $j_2$
$\vdots$
$i_M$ $j_M$

如果存在多种满足条件的方案，输出任意一种都视为正确。

样例 1

输入

5
1 4 2 3 5

输出

Yes
1
3 1

样例 2

输入

2
2 1

输出

No

样例 3

输入

4
3 4 1 2

输出

Yes
3
3 0
1 2
3 0

说明/提示

限制

• $2 \leq N \leq 10^3$
• $P$ 是 $(1,2,\ldots,N)$ 的一个排列
• 输入的所有数均为整数

样例解释 1

以 $i=3, j=1$ 进行操作。此时 $Q=(P_1,P_2,P_5)=(1,4,5)$，所以 $P=(Q_1,P_3,P_4,Q_2,Q_3) = (1,2,3,4,5)$。因此只需一次操作即可将 $P$ 排成升序。

样例解释 2

可以证明，无法在 $2\times 10^3$ 次操作内将 $P$ 排成升序。

样例解释 3

不要求操作次数最小化。

由 ChatGPT 4.1 翻译