E - グラフの問題

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1000

問題文

N 頂点の無向単純グラフであって、各頂点の次数が順に D_1,...,D_N であるようなものが存在するかどうか判定してください。 存在しない場合、ある i に対して D_i1 だけ増やすことで、そのようなグラフが存在するようにできるかどうかも判定してください。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq D_i \leq N-1(1\leq i\leq N)
  • D_i \leq D_{i+1}(1\leq i\leq N-1)
  • 入力はすべて整数である

入力

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

N
D_1
:
D_N

出力

各頂点の次数が順に D_1,...,D_N であるようなものが存在する場合、YES を出力せよ。

そうでない場合、ある i に対して D_i1 だけ増やすことで、そのようなグラフが存在するようにできるなら、NO を出力せよ。

そうでない場合、ABSOLUTELY NO を出力せよ。


入力例 1

5
1
2
2
3
4

出力例 1

YES

辺集合が {(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)} であるようなグラフが条件を満たします。


入力例 2

7
1
1
1
1
6
6
6

出力例 2

ABSOLUTELY NO

入力例 3

8
1
1
1
2
3
4
4
5

出力例 3

NO