Zigzag Breaths Pattern

You are given a sequence of integers representing the number of breaths. The task is to determine whether it is possible to reorder these integers into a zigzag pattern.

A sequence a₀, a₁, a₂, ... , a_n-1 is said to be in a zigzag pattern if it satisfies:

\(a_0 a_2 a_4 < \cdots\)

Your task is to check if such a reordering of the given sequence exists. If it is possible, print YES; otherwise, print NO.

Note: For sequences of length 1 or 2, the answer is always YES since they trivially satisfy the zigzag condition.

inputFormat

The input is read from standard input.

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of elements in the sequence. The second line contains n space-separated integers representing the breaths.

outputFormat

Output a single line containing YES if the sequence can be reordered to form a zigzag pattern, or NO otherwise.

7
4 3 7 8 6 2 1

YES