Vova 的家人正在建造 Vova 长城(由 Vova 自己命名)。沃娃的父母、祖父母、曾祖父母都为此做出了贡献。现在完全由 Vova 来完成收尾工作。
墙的当前状态可以由 $$$n$$$ 整数组成的序列 $$$a$$$ 表示,其中 $$$a_i$$$ 是墙的第 $$$i$$$ 部分的高度。
Vova 只能使用 $$$2 \times 1$$$ 砖块来放入墙壁(不过,他的砖块供应量是无限的)。
Vova 可以将砖块水平放置在相同高度的墙壁的相邻部分上。这意味着,如果对于某些 $$$i$$$,部分 $$$i$$$ 的当前高度与部分 $$$i + 1$$$ 相同,则 Vova 可以在那里放一块砖,从而将两个高度都增加 1。显然,Vova 不能以这样的方式放置砖块,使其部分超出边界(在墙的部分 $$$1$$$ 的左侧或在墙的部分 $$$n$$$ 的右侧)它)。
下一段专门针对问题的版本 1。
Vova 还可以垂直放置砖块。这意味着将墙的任何部分的高度增加 2。
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
YES
输入 #3
2 10 10
输出 #3
YES
输入#4
3 1 2 3
输出#4
NO
注意
在第一个示例中,Vova 可以在第 2 部分和第 3 部分上放置一块砖,以使墙 $$$[2, 2, 2, 2, 5]$$$,然后在第 1 和 2 部分上放置 3 块砖,在第 3 和 4 部分上放置 3 块砖,使其成为 $$$[5, 5, 5, 5, 5]$$$。
在第二个示例中,Vova 可以将一块砖垂直放置在第 3 部分上,使其成为墙 $$$[4, 5, 5]$$$,然后水平放置在第 2 和 3 部分上,使其成为 $$$[4, 6, 6]$$$,然后垂直放置在第 1 部分上,使其成为 $$$[6, 6, 6]$$$。
在第三个示例中,墙已经完成。