Subxor
/

## Algorithms, Greedy Algorithms

Problem
Editorial
Analytics

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$

SAMPLE INPUT
2
2 2
SAMPLE OUTPUT
-1
Explanation

The possible partitions of the array are: , but the xor of both the subarrays is 0 and [2,2] where the xor of this subarray itself is 0. Hence the answer is -1.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...