Equal Array Transformation

You are given an array A containing N integers. You are allowed to perform an operation any number of times, where in each operation, you can add an arbitrary even integer to any element of the array (possibly different for each element).

Your task is to determine whether it is possible to make all elements of the array equal by applying the allowed operation any number of times.

Observation: Adding an even number does not change the parity of an integer. Hence, the array elements can be made equal if and only if all elements have the same parity (i.e. all even or all odd).

For example, if A = [3, 5, 1], all elements are odd so the answer is 1 (possible). However, if A = [1, 2, 3, 4] then the array has mixed parity so the answer is 0 (not possible).

inputFormat

The input is given via standard input (stdin). The first line contains a single integer N, which is the number of elements in the array A. The second line contains N space-separated integers representing the elements of A.

outputFormat

Output a single integer (either 1 or 0) to standard output (stdout). Print 1 if it is possible to make all elements equal using the allowed operations, otherwise print 0.## sample

4
2 2 2 2

1