Sorting by Even-Sum Swaps

You are given an array of n integers. You are allowed to swap two adjacent elements if and only if their sum is even (i.e. both numbers have the same parity). Using any number of such operations, determine whether it is possible to sort the array in non-decreasing order.

Under the constraints of the allowed operation, a necessary and sufficient condition is that the array contains at least one even and at least one odd number. If the array contains only evens or only odds, then no swap is possible with a different parity and the answer is NO. Otherwise, output YES.

Input: The first line contains an integer n (the number of elements). The second line contains n space-separated integers.

Output: Print a single line containing either YES or NO.

inputFormat

The first line of input contains a single integer n, representing the number of elements in the array. The second line contains n space-separated integers which represent the array elements.

outputFormat

Output a single line containing YES if it is possible to sort the array under the given constraints, or NO otherwise.## sample

5
3 5 2 8 6

YES