Two-Way Vote Count - Repovive Starter Round 8 | Repovive

23D. Two-Way Vote Count

2000 pts1s256 MB

There are $n$ votes, represented by the array $a_1, a_2, \ldots, a_n$ . Vote $i$ is for candidate $a_i$ .

You may rearrange the votes in any order. Determine whether there is an arrangement satisfying the following condition:

Whether the votes are counted from left to right or from right to left, after each vote is counted, exactly one candidate has strictly more counted votes than every other candidate.

The two counts are independent: all candidates start with zero counted votes in each direction.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le n$ for all $1 \le i \le n$ .
All input values are integers.

Input

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

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

The second line contains the votes $a_1, a_2, \ldots, a_n$ .

Output

\text{Yes / No}

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

You may print the answer in any combination of uppercase and lowercase letters. For example, Yes, YES, and YeS are all accepted.

Samples

Input

9
1 1 1 1 1 2 2 3 3

Explanation

One valid arrangement is $[1,1,2,3,1,2,3,1,1]$ .

From left to right, candidate $1$ has strictly more counted votes than every other candidate after each vote. The same is true from right to left.

Output

Yes

Input

4
1 1 1 2

Explanation

Any valid arrangement must begin and end with a vote for candidate $1$ ; otherwise, candidate $2$ would lead initially but would not lead after all votes are counted.

The vote for candidate $2$ would then be in one of the two middle positions. Counting from the closer end, the first two votes would give one vote to each candidate, causing a tie.

Output

No

Input

1
1

Explanation

The only vote is for candidate $1$ . After counting it from either direction, candidate $1$ is the unique leader.

Output

Yes

There are $n$ votes, represented by the array $a_1, a_2, \ldots, a_n$ . Vote $i$ is for candidate $a_i$ .

You may rearrange the votes in any order. Determine whether there is an arrangement satisfying the following condition:

Whether the votes are counted from left to right or from right to left, after each vote is counted, exactly one candidate has strictly more counted votes than every other candidate.

The two counts are independent: all candidates start with zero counted votes in each direction.

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le n$ for all $1 \le i \le n$ .
All input values are integers.

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

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

The second line contains the votes $a_1, a_2, \ldots, a_n$ .

\text{Yes / No}

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

You may print the answer in any combination of uppercase and lowercase letters. For example, Yes, YES, and YeS are all accepted.

One valid arrangement is $[1,1,2,3,1,2,3,1,1]$ .

From left to right, candidate $1$ has strictly more counted votes than every other candidate after each vote. The same is true from right to left.

Any valid arrangement must begin and end with a vote for candidate $1$ ; otherwise, candidate $2$ would lead initially but would not lead after all votes are counted.

The vote for candidate $2$ would then be in one of the two middle positions. Counting from the closer end, the first two votes would give one vote to each candidate, causing a tie.

The only vote is for candidate $1$ . After counting it from either direction, candidate $1$ is the unique leader.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

23D. Two-Way Vote Count

Constraints

Input

Output

Samples

23D. Two-Way Vote Count

Constraints

Input

Output

Samples