AT_arc162_b.[ARC162B] Insertion Sort 2

给定一个 $ (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$

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

限制

• $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 翻译