Great Vova Wall (Version 2)
Contest: Codeforces Round 527 (Div. 3)
Difficulty rating: 2200
Tags: data structures, implementation

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 only horizontally on the neighbouring 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).

Note that Vova can't put bricks vertically.

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 no bricks in the wall.

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:
NO

Editorial:
Fairly enough, solutions of both versions of the problem are pretty similar.
Read the second part of the previous tutorial first.
This problem can also be implemented in the strightforward manner. The greedy solution now is searching for the first minimum in array and putting a brick in there. If it's impossible then the answer is "NO". This can also be simulated with sets, a bit more tedious but still ok and also $$$O(n \log n)$$$.
Now back to the stack approach. Here you can't go to parities of the numbers (like tests $$$[1, 3]$$$ and $$$[1, 1]$$$ lead to different results). You push the number itself. However, you will also need an extra condition on the stack. You can't push to it the number greater than the current topmost element.
The only problem with this are maximums of array. Obviously, the resulting wall (if the answer exists) will be of height equal to the maximum initial height. And it means that you shouldn't care about the ability to match all maximums in stack. They way I suggest to take around the issue is to process separately each segment between two consecutive maximums.
One can easily prove the correctness of it by construction.
Overall complexity: $$$O(n)$$$.