Playlist Reordering

You are given a playlist containing n songs, each song is associated with a genre represented by an integer. Your task is to determine whether it is possible to reorder the playlist in such a way that no two consecutive songs share the same genre.

The key observation is that the reordering is possible if and only if the maximum frequency among all genres, denoted as \(\text{max}_{\text{freq}}\), satisfies the following condition:

\(\text{max}_{\text{freq}} \leq \lceil \frac{n}{2} \rceil\)

If this condition is not met, then it is impossible to rearrange the songs without having at least two adjacent songs of the same genre.

Input Constraints: \(1 \leq n \leq 10^5\). Each genre is represented by a positive integer.

inputFormat

The first line contains an integer n, the number of songs in the playlist.

The second line contains n space-separated integers representing the genre of each song.

outputFormat

Output a single line containing YES if it is possible to reorder the playlist so that no two consecutive songs have the same genre. Otherwise, output NO.

5
1 1 2 2 3

YES