Duty Roster

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given N duty days with soldier numbers, decide whether the roster can be rearranged so no soldier is on duty on two consecutive days.

Level: Easy3 of 10
Topics: Hash map, Greedy
Solved: No attempts yet

Problem

The battalion of company commander Mansik keeps a duty roster that lists the duty schedule for $N$ days. Each day has one soldier on duty, and the roster records that soldier's number. Soldiers need enough rest after a duty shift, so the same soldier is strictly forbidden from serving duty on two consecutive days.

To avoid breaking this rule, Mansik wants to improve the roster by swapping the duty order of soldiers as many times as he likes. Determine whether the roster can be improved so that no soldier serves duty on two consecutive days.

Input

The first line contains the number of days $N$ in the schedule. $(1\leq N\leq 100\,000)$

The second line contains $N$ integers $a_1,\cdots,a_N$ separated by spaces, where $a_i$ is the number of the soldier on duty on day $i$ . $(1\leq a_i\leq 100\,000)$

Output

Print YES if the roster can be improved so that no soldier is on duty on two consecutive days. Otherwise, print NO.

Examples3

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