在同类相食的猫咪王国中，猫咪 Ket 刚刚得知明天将举办全国猫咪日（NCD）。作为被任命的软件工程师，他的任务是开发一个系统来汇报同类相食的情况。
有 $n$ 只猫参加 NCD 庆典，编号为 $1$ 到 $n$。第 $i$ 只猫的幸福度为 $h[i]$。在任何时间点，一只猫可以吃掉另一只幸福度严格小于它的猫。在此之后，较幸福的猫的幸福度会增加 1，并且它不能再吃任何其他猫。此外，较不幸福的猫会消失。
Ket 的任务是确定是否可能在庆典结束时只剩下一只猫。这意味着所有其他猫都被吃掉了。
输入格式
您的程序必须从标准输入读入。
第一行包含一个整数 $n$。
第二行包含 $n$ 个空格分隔的整数 $h[1], h[2], \dots, h[n]$。
输出格式
您的程序必须输出到标准输出。
如果庆典后可能只剩下一只猫，则输出 YES，否则输出 NO。
数据范围
对于所有测试数据，输入满足以下范围：
- $2 \le n \le 200\,000$
- 对于所有 $1 \le i \le n$，$0 \le h[i] \le 10^9$
您的程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 0 | 0 | 样例 |
| 1 | 8 | $n = 2$ |
| 2 | 10 | $n \le 3$ |
| 3 | 6 | $h[1] = h[n]$ |
| 4 | 18 | $n \le 1000$ |
| 5 | 28 | $h$ 单调不减（对于所有 $1 \le i \le n - 1$，$h[i] \le h[i + 1]$） |
| 6 | 30 | 无附加限制 |
样例
输入 1
2 3141 59
输出 1
YES
说明 1
此测试点适用于子任务 1, 2, 4 和 6。
输入 2
3 31 41 59
输出 2
YES
说明 2
此测试点适用于子任务 2, 4, 5 和 6。
有 $n = 3$ 只猫，幸福度分别为 31, 41 和 59。如果第二只猫吃掉第一只猫，随后被第三只猫吃掉，那么庆典结束时就可能只剩下一只猫。
输入 3
5 10 0 24 25 10
输出 3
NO
说明 3
此测试点适用于子任务 3, 4 和 6。
猫咪们无法以任何方式互相捕食从而在庆典结束时只剩下一只猫。
输入 4
6 2 25 11 5 20 26
输出 4
NO
说明 4
此测试点适用于子任务 4 和 6。