You are given an array ~a~ of ~N~ binary integers. You are to print 1 if there is an odd number of ~1~s in ~a~, and 0 otherwise.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~.

The next line will contain ~N~ binary integers, ~a_1, a_2, a_3, \ldots, a_N~ ~(a_i \in{\{0,1\}})~.

Output Specification

Output 1 if there is an odd number of ~1~s in ~a~, and 0 otherwise.

Sample Input

5
1 0 1 1 1

Sample Output

0