D - Yet Another Balls and Boxes Problem Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

ここに N 個の箱があり、箱 i には A_i 個のボールが入っています。あなたは、以下の操作を 0 回以上 2 \times 10^6 回以下行うことができます。

  • 整数対 (X,Y)(X \neq Y) であって、「箱 X に入っているボールの個数」が「箱 Y に入っているボールの個数」以下であるものを選ぶ。

    そして、箱 X に入っているボールの数だけ箱 Y から箱 X にボールを移す。

一つの箱にすべてのボールが入っている状態にできるか判定し、可能ならば操作列を一つ構築してください。

制約

  • 2 \le N \le 10^5
  • 1 \le A_i \le 10^5
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

すべてのボールが一つの箱に入っている状態にすることが不可能ならば No と出力せよ。可能な場合、操作回数を M 、 i 回目に選んだ (X,Y) を (P_i,Q_i) として以下の形式で出力せよ。

Yes
M
P_1 Q_1
P_2 Q_2
\vdots
P_M Q_M

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

3
1 3 4

出力例 1

Yes
3
1 2
2 1
3 2

以下のように操作が行われます。

  1. 箱 2 から箱 1 にボールを 1 つ移す。
  2. 箱 1 から箱 2 にボールを 2 つ移す。
  3. 箱 2 から箱 3 にボールを 4 つ移す。

最終的に箱 3 にボールが 8 つ入っている状態になります。

なお、たとえば次のような出力も正解とみなされます。

Yes
3
1 2
1 2
1 3

入力例 2

4
7 2 3 1

出力例 2

No

2\times 10^6 回以内の操作では一つの箱にすべてのボールが入っている状態にできないことが証明できます。

入力例 3

5
2 6 2 1 5

出力例 3

Yes
6
4 5
1 2
4 3
2 1
5 4
5 2