Rearranging Array with Alternating Parity

You are given an array of n integers. Your task is to determine if it is possible to rearrange the array such that consecutive elements have different parity (i.e. one is even and the other odd).

In other words, if we let even be the count of even numbers and odd be the count of odd numbers, then a necessary and sufficient condition for such a rearrangement to exist is:

$$|even - odd| \le 1$$

Print YES if it is possible to form such an arrangement, otherwise print NO.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains a single integer n representing the number of elements in the array.
2. The second line contains n space-separated integers.

outputFormat

Output a single line to standard output (stdout) containing either YES if the array can be rearranged so that adjacent elements have different parity, or NO otherwise.

4
2 3 4 5

YES