Vova 家族正在建造 Vova 长城(由 Vova 本人命名)。沃娃的父母、祖父母、曾祖父母都为此做出了贡献。现在完全由 Vova 来完成收尾工作。
墙的当前状态可以用 $$$n$$$ 整数的序列 $$$a$$$ 表示,其中 $$$a_i$$$ 是墙的第 $$$i$$$ 部分的高度。
Vova 只能使用 $$$2 \times 1$$$ 砖块来放入墙壁(不过,他的砖块供应量是无限的)。
Vova 只能将砖块水平放置在相同高度的墙的相邻部分上。这意味着,如果对于某些 $$$i$$$,部分 $$$i$$$ 的当前高度与部分 $$$i + 1$$$ 相同,则 Vova 可以在那里放一块砖,从而将两个高度都增加 1。显然,Vova 不能以这样的方式放置砖块,使其部分超出边界(在墙的部分 $$$1$$$ 的左侧或在墙的部分 $$$n$$$ 的右侧)它)。
请注意,Vova 无法垂直放置砖块。
Vova 是一位完美主义者,因此他认为墙在以下情况下已完成:
- 墙的所有部分都具有相同的高度;
- 墙内没有空白空间。
Vova 可以使用任意数量的砖块(可能是零)来完成这堵墙吗?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 墙中的部分数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 墙各部分的初始高度。
输出
如果 Vova 可以使用任意数量的砖块(可能为零)完成墙,则打印“YES”。
否则打印“NO”。
示例
输入 #1
5 2 1 1 2 5
输出 #1
YES
输入 #2
3 4 5 3
输出 #2
NO
输入 #3
2 10 10
输出 #3
YES
注意
在第一个示例中,Vova 可以在第 2 部分和第 3 部分上放置一块砖,以使墙 $$$[2, 2, 2, 2, 5]$$$,然后在第 1 部分和第 2 部分上放置 3 块砖,在第 3 部分和第 4 部分上放置 3 块砖,使其成为 $$$[5, 5, 5, 5, 5]$$$。
在第二个示例中,Vova 不能在墙上放置砖块。
在第三个示例中,墙已经完成。