配点 : 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