← 返回题目列表

AtCoder · arc162_b

B. 插入排序2

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

分数: 500 点

问题陈述

排列 给出了 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) 。

判断是否可以重新排列 最多执行以下操作按升序排列 P 最多执行以下操作按升序排列 2\times 10^3 次,如果可能的话,显示一个这样的操作序列。

  • 选择整数 i 和 j 这样 1\leq i \leq N-1,0 \leq j \leq N-2。让 Q = (Q_1, Q_2,\ldots,Q_{N-2}) 是通过删除获得的序列 (P_i,P_{i+1}) 来自 P。更换 P 与 (Q_1,\ldots,Q_j, P_i, P_{i+1}, Q_{j+1},\ldots,Q_{N-2}).

约束

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

输入

输入由标准输入按以下格式给出:

N
P_1 P_2 \ldots P_N

输出

If P 不能在以下时间内按升序重新排列 2\times 10^3 操作,打印 No。如果可以按升序重新排列,则令 M\ (0 \leq M \leq 2\times 10^3) 是操作次数,并且 i_k,j_k 被选中 i,j 为 k第次操作 (1\leq k \leq M),并按以下格式打印:

Yes
M
i_1 j_1
i_2 j_2
\vdots
i_M j_M

如果有多个解决方案,则其中任何一个都将被视为正确。


示例输入 1

5
1 4 2 3 5

示例输出 1

Yes
1
3 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
2 1

示例输出 2

No

可以证明 P 不能在以下时间内按升序重新排列 2\times 10^3 操作。


示例输入 3

4
3 4 1 2

示例输出 3

Yes
3
3 0
1 2
3 0

无需最小化操作次数。