Nearest Rival - Repovive Starter Round 8 | Repovive

23C. Nearest Rival

1500 pts1s256 MB

There are $n$ people standing in a row, numbered from $1$ to $n$ . Each person belongs to either the red team or the blue team, and both teams are non-empty.

The distance between people $i$ and $j$ is $|i-j|$ .

Each person reports the distance to the nearest person belonging to the other team. Their reports form an array $a_1,a_2,\ldots,a_n$ .

Determine whether it is possible to assign people to the two teams so that every report is correct.

Constraints

$2 \le n \le 2 \times 10^5$
$1 \le a_i \le n-1$

Input

\begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

The first line contains the number of people $n$ .

The second line contains their reports $a_1,a_2,\ldots,a_n$ .

Output

\text{answer}

Print Yes if a valid assignment exists, and No otherwise.

You may print each letter in either uppercase or lowercase. For example, YES, Yes, and YeS are all accepted.

Samples

Input

6
1 1 2 2 1 1

Explanation

One valid team assignment is RBBBBR, where R denotes the red team and B denotes the blue team. The first and last people each have a rival at distance $1$ . The four people between them have nearest rivals at distances $1,2,2,1$ , respectively.

Output

Yes

Input

3
1 2 1

Explanation

The first person's report forces the first two people to belong to different teams. The second person then has a rival at distance $1$ , contradicting their report of $2$ .

Output

No

Input

5
2 1 1 1 2

Explanation

One valid team assignment is RRBRR. The middle person has an adjacent rival. For the other four people, the nearest rival is the middle person, at distances $2,1,1,2$ , respectively.

Output

Yes

There are $n$ people standing in a row, numbered from $1$ to $n$ . Each person belongs to either the red team or the blue team, and both teams are non-empty.

The distance between people $i$ and $j$ is $|i-j|$ .

Each person reports the distance to the nearest person belonging to the other team. Their reports form an array $a_1,a_2,\ldots,a_n$ .

Determine whether it is possible to assign people to the two teams so that every report is correct.

$2 \le n \le 2 \times 10^5$
$1 \le a_i \le n-1$

\begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

The first line contains the number of people $n$ .

The second line contains their reports $a_1,a_2,\ldots,a_n$ .

\text{answer}

Print Yes if a valid assignment exists, and No otherwise.

You may print each letter in either uppercase or lowercase. For example, YES, Yes, and YeS are all accepted.

The first person's report forces the first two people to belong to different teams. The second person then has a rival at distance $1$ , contradicting their report of $2$ .

One valid team assignment is RRBRR. The middle person has an adjacent rival. For the other four people, the nearest rival is the middle person, at distances $2,1,1,2$ , respectively.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

23C. Nearest Rival

Constraints

Input

Output

Samples

23C. Nearest Rival

Constraints

Input

Output

Samples