You are provided an array $A$ of $n$ integers. You are required to partition the array into the minimum number of subarrays such that the $XOR$ of any non-empty subset of the subarrays is not equal to zero. If no such partition exists, then print $-1$. Otherwise, print 1.

Note:

• A subarray is a non-empty contiguous subsequence of an array.
• The $XOR$ of a set of subarrays is defined as the sum of determined $XORs$ of the numbers in all the subarrays when accumulated.

Input format

The first line consists of an integer $n$ that is followed by $n$ space-separated integers.

Output format

Print the answer in a single line.

Constraints

$1\leq n\leq 5*10^5$

$0\leq A[i]\leq 10^9$