Reorganization

Interview

Time limit2sMemory limit512 MB

Summary

Given each employee's rank in ID order, decide whether a binary hierarchy exists where every non-root has a supervisor with a smaller ID and a better rank.

Level: Medium6 of 10
Topics: Greedy, Tree, Stack, Implementation
Solved: No attempts yet

Problem

Alice and Bob run a company together, and they want to reorganize it into a single hierarchy.

There are $n$ employees. Each employee has a distinct employee ID from $1$ to $n$ , and a distinct integer rank $R$ ; a smaller rank value means a higher rank.

Decide whether the company can be organized so that all of the following hold:

Exactly one employee is the director, who has no supervisor.
Every employee except the director has exactly one direct supervisor, whose employee ID is smaller and whose rank is higher (that is, whose rank value is smaller).
Each employee directly supervises at most $2$ people.

Input

The first line contains the number of employees $n$ ( $1 \le n \le 100{,}000$ ).

Each of the next $n$ lines contains one integer: the $i$ -th of these lines gives the rank $R$ ( $1 \le R \le 10{,}000{,}000$ ) of the employee whose ID is $i$ . All rank values are distinct.

Output

Print YES if the company can be reorganized as required, and NO otherwise.

Examples2

Example 1
Input
```
6
1
6
5
2
3
4
```
Expected output
```
NO
```
Example 2
Input
```
6
1
6
2
3
4
5
```
Expected output
```
YES
```