Zigzag Rearrangement

You are given a list of integers representing the heights of plants. Your task is to determine if it is possible to rearrange these heights so that they form a zigzag pattern.

A sequence \(a_1, a_2, \ldots, a_n\) is said to be in zigzag order if for every \(2 \le i \le n-1\), one of the following holds:

• \(a_i > a_{i-1}\) and \(a_i > a_{i+1}\)
• \(a_i < a_{i-1}\) and \(a_i < a_{i+1}\)

If there is only one plant, the pattern is automatically considered zigzag.

For example, given the heights 4 3 7 8 2, one possible rearrangement is 2 8 3 7 4, which forms a zigzag since:

• \(8 > 2\) and \(8 > 3\)
• \(3 < 8\) and \(3 < 7\)
• \(7 > 3\) and \(7 > 4\)

Output YES if such a rearrangement exists, otherwise output NO.

inputFormat

The first line contains a single integer (n) — the number of plants. The second line contains (n) space-separated integers representing the heights of the plants.

outputFormat

Print a single line containing the string "YES" if the heights can be rearranged into a zigzag pattern, or "NO" otherwise.## sample

1
5

YES