题目描述

在食人猫的王国里，猫 Ket 刚刚得知明天将是国家猫日（NCD）。作为指定的软件工程师，他负责开发一个系统来报告吃猫情况。

共有 $n$ 只猫参加 NCD 庆祝活动，编号从 $1$ 到 $n$。第 $i$ 只猫的快乐值为 $h[i]$。在任何时刻，一只猫可以吃掉一只 严格 不快乐的猫。此事发生后，较快乐的猫的快乐值 增加 $1$，并且它 不能再吃其他任何猫。此外，较不快乐的猫消失。

Ket 的任务是确定是否可能最终只剩下一只猫。这意味着所有其他猫都被吃掉了。

输入格式

你的程序必须从标准输入中读取数据。

输入的第一行包含一个整数 $n$。

输入的第二行包含 $n$ 个以空格分隔的整数 $h[1], h[2], \ldots, h[n]$。

输出格式

你的程序必须输出到标准输出。

如果庆祝活动后可能只剩下一只猫，则输出 YES，否则输出 NO。

2
3141 59

YES

3
31 41 59

YES

5
10 0 24 25 10

NO

6
2 25 11 5 20 26

NO

提示

样例测试用例 2 解释

有 $n = 3$ 只猫，快乐值分别为 $31$、$41$ 和 $59$。如果第二只猫吃掉第一只猫，随后被第三只猫吃掉，那么最终可能只剩下一只猫。

样例测试用例 3 解释

猫无法通过互相吞食的方式最终只剩下一只猫。

子任务

对于所有测试用例，输入均满足以下范围：

• $2 \le n \le 200\,000$
• 对于所有 $1 \le i \le n$，$0 \le h[i] \le 10^9$

你的程序将在满足以下限制的输入实例上进行测试：

翻译由 DeepSeek 完成