B - Insertion Sort 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます。

P に対し以下の操作を 2\times 10^3 回以下行うことで P を昇順に並び替えられるか判定し、可能な場合は実際に操作手順を一つ示してください。

  • 1\leq i \leq N-1,0 \leq j \leq N-2 を満たす整数 i,j を選ぶ。Q = (Q_1, Q_2,\ldots,Q_{N-2})P から (P_i,P_{i+1}) を抜き出して得られる列としたとき、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

出力

2\times 10^3 回以下の操作で P を昇順に並び替えられない場合 No を出力せよ。昇順に並び替えられる場合、操作回数を M\ (0 \leq M \leq 2\times 10^3) とし、k 回目 (1\leq k \leq M) の操作で選んだ i,ji_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

出力例 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) となります。

よって 1 回の操作で P を昇順に並び替えられます。


入力例 2

2
2 1

出力例 2

No

2\times 10^3 回以下の操作では P を昇順に並び替えられないことが証明できます。


入力例 3

4
3 4 1 2

出力例 3

Yes
3
3 0
1 2
3 0

操作回数を最小化する必要はありません。

Score : 500 points

Problem Statement

A permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) is given.

Determine whether it is possible to rearrange P in ascending order by performing the following operation at most 2\times 10^3 times, and if possible, show one such sequence of operations.

  • Choose integers i and j such that 1\leq i \leq N-1,0 \leq j \leq N-2. Let Q = (Q_1, Q_2,\ldots,Q_{N-2}) be the sequence obtained by removing (P_i,P_{i+1}) from P. Replace P with (Q_1,\ldots,Q_j, P_i, P_{i+1}, Q_{j+1},\ldots,Q_{N-2}).

Constraints

  • 2 \leq N \leq 10^3
  • P 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
P_1 P_2 \ldots P_N

Output

If P cannot be rearranged in ascending order within 2\times 10^3 operations, print No. If it can be rearranged in ascending order, let M\ (0 \leq M \leq 2\times 10^3) be the number of operations, and i_k,j_k be the chosen i,j for the k-th operation (1\leq k \leq M), and print them in the following format:

Yes
M
i_1 j_1
i_2 j_2
\vdots
i_M j_M

If there are multiple solutions, any of them will be considered correct.


Sample Input 1

5
1 4 2 3 5

Sample Output 1

Yes
1
3 1

Perform the operation with i=3,j=1.

Then, Q=(P_1,P_2,P_5)=(1,4,5), so you get P=(Q_1,P_3,P_4,Q_2,Q_3) = (1,2,3,4,5).

Thus, P can be rearranged in ascending order with one operation.


Sample Input 2

2
2 1

Sample Output 2

No

It can be proved that P cannot be rearranged in ascending order within 2\times 10^3 operations.


Sample Input 3

4
3 4 1 2

Sample Output 3

Yes
3
3 0
1 2
3 0

There is no need to minimize the number of operations.