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\)