Zigzag Array Rearrangement

You are given an array of n integers representing the heights of flowers. Your task is to determine whether it is possible to rearrange the array such that the flower heights form a zigzag pattern.

A sequence a₁, a₂, ..., a_n is said to be in a zigzag pattern if for every index i (2 ≤ i ≤ n-1), one of the following holds:

• a_i-1 < a_i > a_i+1 (local maximum)
• a_i-1 > a_i < a_i+1 (local minimum)

In mathematical terms, for each valid i (2 ≤ i ≤ n-1), the following condition must hold: $$ \big((a_{i-1} a_{i+1}) \quad \text{or} \quad (a_{i-1} > a_i < a_{i+1})\big). $$

If the array has less than three elements, it is always possible to form a zigzag pattern.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵) representing the number of flowers.

The second line contains n space-separated integers representing the heights of the flowers.

outputFormat

Output a single line containing "YES" if it is possible to rearrange the array into a zigzag pattern, otherwise output "NO".

## sample

5
4 3 7 8 2

YES

</p>