Great Vova Wall (Version 1)
Contest: Codeforces Round 527 (Div. 3)
Difficulty rating: 2200
Tags: greedy, implementation, math

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)?

Input format:
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.

Output format:
Print "YES" if Vova can complete the wall using any amount of bricks (possibly zero).

Print "NO" otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
5
2 1 1 2 5

Example output:
YES

Example input:
3
4 5 3

Example output:
YES

Editorial:
Fairly enough, solutions of both versions of the problem are pretty similar.
The major difference between them are the vertical bricks. As you aren't required to minimize the total height, you can work not with the heights themselves but with their parities instead. Vertical brick now does nothing and horizontal brick changes the parity of neighbouring parts of the same parity.
Now imagine the following greedy solution. While you have some segment of the same parities of even length, fill it with horizontal bricks. This operation merges this segment with one to the left and to the right. If there is a single segment left then the answer is "YES". Otherwise it's "NO". The proof is left to the readers.
Implementing this as it is will be $$$O(n \log n)$$$ at best. You'll need to keep the whole set of segments and the set with only even length ones.
But there exists more fun approach.
We don't even need the lengths of the segments — just the parities of the lengths. Then merging the even segment with something will just erase that segment and xor the length of the left and right ones. Moreover, you don't even need to erase the whole even segment, you can do it brick by brick, as this operations are now the same.
Let's simulate this with a stack. When the new number comes, push its parity to the stack. If the topmost two elements of the stack have the same parity, pop them both. Now the answer is "YES" if at the end stack has no more than one element.
When I heard of this problem, I actually had not that stack itself in mind but the correct bracket sequences. Like let's define parity 0 as '(' and ')' and parity 1 as '[' and ']'. Now the operations we perform with stack are "greedily put the closing bracket if the last unclosed bracket was of the same type" and "put opening otherwise". Then the stack will have like all the brackets which are still to be closed and you'll close them as early as you can. This idea helped to both prove the correctness of algo and implement it.
Overall complexity: $$$O(n)$$$.