题目背景

小明和小红在一个环形轨道上玩取数游戏。

题目描述

有一个环形轨道，上面有 $n$ 条边，每条边上有一个非负整数。这些整数中至少有一个 $0$。

一枚硬币放在环上的某个节点上。两人轮流操作，每次可以选择硬币左边或右边一条数值非 $0$ 的边，将该边上的数减小到任意非负整数（必须严格减小），然后将硬币移动到该边的另一端。

如果轮到某人操作时，硬币左右两边的边上的数值都是 $0$，则该人输。

判断先手方是否有必胜策略。

输入格式

第一行一个整数 $n$，表示边的数量。
第二行 $n$ 个非负整数 $a_0, a_1, \ldots, a_{n-1}$，表示每条边上的数值。

输出格式

如果先手有必胜策略，输出 YES，否则输出 NO。

样例

4
2 5 3 0

YES

3
0 0 0

NO

提示

本题的关键在于环上至少有一个 $0$，它将环断开。

数据范围

• 对于 $30\%$ 的数据，$n \le 10$
• 对于 $100\%$ 的数据，$2 \le n \le 10^6$，$0 \le a_i \le 10^9$