Great Vova Wall (Version 1)

题意翻译

### 题意简述 给定一个序列 $a=\{a_1,a_2,\dots,a_n\}$，有以下两种操作： - 若 $a_i=a_{i\ +\ 1}$，则可将 $a_i$ 与 $a_{i\ +\ 1}$（$1\le i < n$）同时加 $1$； - 将 $a_i$（$1\le i\le n$）加 $2$。 求问是否可经过多此操作后使得所有 $a_i$ 相等。 ------------ ### 题目描述 Vova 在建一堵墙（Vova 美名其曰“The Great Vova Wall”）。此时有序列 $a=\{a_1,a_2,\dots,a_n\}$，其中 $a_i$ 表示墙体第 $i$ 部分的高度。 _（注：此问题中假设 Vova 的砖头无限且只能用 $2\times 1$ 的砌墙）_ Vova 可以将砖头水平放置或垂直放置。当然水平放置时不可让砖头“越界”，即砖头不可有部分位于第 $1$ 部分的左边或位于第 $n$ 部分的右边。水平放置时砖头将会使第 $i$ 和 $i+1$ 部分高度 $+\ 1$，垂直放置时则将其所在的位置高度 $+\ 2$。 重度强迫症患者兼完美主义者 Vova 认为所有部分高度相等以及墙内没有空隙时这堵墙才算完工。 **** ### 输入格式 第一行包含一个整数 $n$（$1\leqslant n\leqslant 2\times10^5$），表示墙体部分数。 第二行包含 $n$ 个数 $a_1,a_2,\cdots,a_n$（$1\le a_i\le 10^9$），表示墙体高度的初始值。 **** ### 输出格式 若 Vova 可以添加砖块使得墙体完工输出`YES`，否则输出`NO`。 ------------ ### 样例说明 【样例 $1$】 初始：$[2,1,1,2,5]$； 第一次操作：$[2,1+1,1+1,2,5]$； 第二次操作：$[2+1\times 3,2+1\times 3,2,2,5]$； 第三次操作：$[5,5,2+1\times 3,2+1\times 3,5]$； 最终序列：$[5,5,5,5,5]$。 【样例 $2$】 初始：$[4,5,3]$； 第一次操作：$[4,5,3+2]$； 第二次操作：$[4,5+1,5+1]$； 第三次操作：$[4+2,6,6]$； 最终序列：$[6,6,6]$。 【样例 $3$】 初始：$[10,10]$； 最终序列：$[10,10]$。 【样例 $4$】 初始序列：$[1,2,3]$； 此序列无法通过题目给定操作完工。

题目描述

Vova's family is building the Great Vova Wall (named by Vova himself). Vova's parents, grandparents, grand-grandparents contributed to it. Now it's totally up to Vova to put the finishing touches. The current state of the wall can be respresented by a sequence $ a $ of $ n $ integers, with $ a_i $ being the height of the $ i $ -th part of the wall. Vova can only use $ 2 \times 1 $ bricks to put in the wall (he has infinite supply of them, however). Vova can put bricks horizontally on the neighboring parts of the wall of equal height. It means that if for some $ i $ the current height of part $ i $ is the same as for part $ i + 1 $ , then Vova can put a brick there and thus increase both heights by 1. Obviously, Vova can't put bricks in such a way that its parts turn out to be off the borders (to the left of part $ 1 $ of the wall or to the right of part $ n $ of it). The next paragraph is specific to the version 1 of the problem. Vova can also put bricks vertically. That means increasing height of any part of the wall by 2. Vova is a perfectionist, so he considers the wall completed when: - all parts of the wall has the same height; - the wall has no empty spaces inside it. Can Vova complete the wall using any amount of bricks (possibly zero)?

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of parts in the wall. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the initial heights of the parts of the wall.

输出格式

Print "YES" if Vova can complete the wall using any amount of bricks (possibly zero). Print "NO" otherwise.

输入输出样例

输入样例 #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

说明

In the first example Vova can put a brick on parts 2 and 3 to make the wall $ [2, 2, 2, 2, 5] $ and then put 3 bricks on parts 1 and 2 and 3 bricks on parts 3 and 4 to make it $ [5, 5, 5, 5, 5] $ . In the second example Vova can put a brick vertically on part 3 to make the wall $ [4, 5, 5] $ , then horizontally on parts 2 and 3 to make it $ [4, 6, 6] $ and then vertically on part 1 to make it $ [6, 6, 6] $ . In the third example the wall is already complete.