题目描述

Aoi 在雪地里玩耍。在 Aoi 面前，有 $N$ 个雪球从左到右排成一列，编号为 $1$ 到 $N$。第 $i$ 个雪球初始时的大小为 $A_i$。

Aoi 希望她能造出一个大雪球。为此，Aoi 决定重复以下操作，直到雪球的数量变为 $1$ 或无法进行操作：

• 选择相邻的两个雪球，假设左侧的雪球大小为 $l$，右侧的雪球大小为 $r$，则需要满足 $0\le l-r\le 1$；
• 将选定的两个雪球合并成一个大小为 $l+r$ 的雪球；
• 换句话说，如果操作前有 $k$ 个雪球，从左到右大小分别为 $s_1,s_2,\ldots,s_k$，则可以选择一个 $t(1\le t\le k-1)$ 满足 $0\le s_t-s_{t+1}\le 1$ 进行操作，操作后的 $k-1$ 个雪球从左到右大小分别为 $s_1,s_2,\ldots,s_{t-1},s_t+s_{t+1},s_{t+2},\ldots,s_k$。

判断 Aoi 是否能通过操作将所有雪球合并成一个大雪球。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出一行一个字符串，如果可以合成一个大雪球输出 Yes，否则输出 No。

5
1 1 1 1 1

Yes

3
2 2 2

No

8
5 4 3 2 1 2 3 4

No

16
3 2 1 6 2 1 3 2 1 3 12 6 1 1 1 2

Yes

提示

【样例解释 #1】

Aoi 可以通过执行以下操作合成一个大雪球：

• 选择从左到右第 $4$ 和第 $5$ 个雪球，操作后雪球大小变为 $1,1,1,2$；
• 选择从左到右第 $1$ 和第 $2$ 个雪球，操作后雪球大小变为 $2,1,2$；
• 选择从左到右第 $1$ 和第 $2$ 个雪球，操作后雪球大小变为 $3,2$；
• 选择从左到右第 $1$ 和第 $2$ 个雪球，操作后雪球大小变为 $5$。

该样例满足所有子任务的限制。

【样例解释 #2】

Aoi 无法通过执行操作合成一个大雪球。

该样例满足所有子任务的限制。

【样例解释 #3】

该样例满足子任务 $2,3,4,5$ 的限制。

【样例解释 #4】

该样例满足子任务 $3,4,5$ 的限制。

【数据范围】

• $2\le N\le 5\times 10^5$；
• $1\le A_i\le 10^{12}(1\le i\le N)$。

【子任务】

1. （$15$ 分）$A_1=A_2=\cdots=A_N$；
2. （$18$ 分）$N\le 8$；
3. （$18$ 分）$N\le 200$；
4. （$19$ 分）$N\le 5000$；
5. （$30$ 分）无附加限制。