Alternating Parity Reordering

You are given a sequence of n integers. Your task is to determine whether it is possible to reorder the sequence such that no two adjacent numbers share the same parity (i.e. both are even or both are odd).

Recall that an integer is either even or odd. For an arrangement to have alternating parity, every two consecutive numbers must satisfy:

This condition is necessary and sufficient for a valid reordering. If it holds, output Yes; otherwise, output No.

Note: You may reorder the sequence arbitrarily.

inputFormat

The input is given via standard input and consists of two lines:

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

outputFormat

Print a single line to standard output. Output Yes if there exists a reordering of the sequence such that no two adjacent elements have the same parity, otherwise output No.

5
1 2 3 4 5

Yes