← 返回题目列表

Codeforces · 1092/D1

D1. 沃瓦长城(版本 1)

中文机器翻译题面 查看原题

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]$$$。

在第三个示例中,墙已经完成。