Arrange Books Without Adjacent Same Colors

You are given n books. Each book is described by an index and a color. Your task is to determine whether it is possible to arrange all the books in a row so that no two adjacent books have the same color.

It can be proven that an arrangement is possible if and only if the maximum frequency of any single color does not exceed \(\lceil \frac{n}{2} \rceil\). In other words, let \(M\) be the maximum occurrence of any color, then the arrangement is possible if:

\(M \leq \lceil \frac{n}{2} \rceil\)

Output YES if such an arrangement exists and NO otherwise.

inputFormat

The first line contains an integer n, the number of books. Each of the following n lines contains an integer and a string separated by a space, representing the book's index and its color.

outputFormat

Output a single line containing either YES or NO indicating if it is possible to arrange the books such that no two adjacent books have the same color.## sample

4
1 red
2 blue
3 red
4 green

YES