← 返回题目列表

AtCoder · yahoo_procon2018_qual_e

E. 绘图问题

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

配点 : 1000 点

問題文

N 请判断是否存在一个顶点的无向简单图,其各顶点的度依次为 D_1,...,D_N 。 如果不存在,还请判断是否只增加一个 i 反对 D_i 该值应乘以 1 ,就能使这样的图存在。

制約

  • 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_i 该值应乘以 1 只需要增加,就可以让那样的图存在,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