Alternating Zigzag Arrangement

You are given an array of ( n ) integers. Your task is to determine whether it is possible to rearrange the array such that it forms an alternating (zigzag) pattern. An array ( a ) is said to be alternating if for every index ( i ) (where ( 1 \le i \le n-2 )), either ( a[i] > a[i-1] ) and ( a[i] > a[i+1] ) or ( a[i] < a[i-1] ) and ( a[i] < a[i+1] ). For arrays of length 1 or 2, the array trivially satisfies the condition.

In other words, after some rearrangement, for each valid index ( i ) with ( 1 \le i \le n-2 ), the following must hold: [ (a[i] > a[i-1] \text{ and } a[i] > a[i+1]) \quad \text{or} \quad (a[i] < a[i-1] \text{ and } a[i] < a[i+1]). ] If such a rearrangement exists, output "YES"; otherwise, output "NO".

inputFormat

The input is read from standard input (stdin). The first line contains an integer ( n ) representing the number of elements in the array. The second line contains ( n ) space-separated integers representing the elements of the array.

outputFormat

Output a single line to standard output (stdout) containing "YES" if it is possible to rearrange the array into an alternating zigzag pattern, and "NO" otherwise.## sample

5
1 3 2 4 5

YES