CF1101G.(Zero XOR Subset)-less

You are given an array $a_1, a_2, \dots, a_n$ of integer numbers.

Your task is to divide the array into the maximum number of segments in such a way that:

• each element is contained in exactly one segment;
• each segment contains at least one element;
• there doesn't exist a non-empty subset of segments such that bitwise XOR of the numbers from them is equal to $0$.

Print the maximum number of segments the array can be divided into. Print -1 if no suitable division exists.

给你一个整数数组 $a_1, a_2, \dots, a_n$。

你的任务是将该数组划分为尽可能多的段，使得满足以下条件：

• 每个元素恰好属于一个段；
• 每个段至少包含一个元素；
• 不存在一个非空的段子集，使得这些段中所有数字的按位异或（XOR）结果等于 $0$。

请输出该数组所能划分出的最大段数；若不存在满足条件的划分方式，则输出 -1。

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$).

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 数组的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）。

Print the maximum number of segments the array can be divided into while following the given constraints. Print -1 if no suitable division exists.

在满足给定约束条件下，输出数组最多能被划分成的段数。若不存在满足条件的划分方式，则输出 $-1$。

In the first example $2$ is the maximum number. If you divide the array into ${[5], [5, 7, 2]}$, the XOR value of the subset of only the second segment is $5 \oplus 7 \oplus 2 = 0$. ${[5, 5], [7, 2]}$ has the value of the subset of only the first segment being $5 \oplus 5 = 0$. However, ${[5, 5, 7], [2]}$ will lead to subsets ${[5, 5, 7]}$ of XOR $7$, ${[2]}$ of XOR $2$ and ${[5, 5, 7], [2]}$ of XOR $5 \oplus 5 \oplus 7 \oplus 2 = 5$.

Let's take a look at some division on $3$ segments — ${[5], [5, 7], [2]}$. It will produce subsets:

• ${[5]}$, XOR $5$;
• ${[5, 7]}$, XOR $2$;
• ${[5], [5, 7]}$, XOR $7$;
• ${[2]}$, XOR $2$;
• ${[5], [2]}$, XOR $7$;
• ${[5, 7], [2]}$, XOR $0$;
• ${[5], [5, 7], [2]}$, XOR $5$;

As you can see, subset ${[5, 7], [2]}$ has its XOR equal to $0$, which is unacceptable. You can check that for other divisions of size $3$ or $4$, non-empty subset with $0$ XOR always exists.

The second example has no suitable divisions.

The third example array can be divided into ${[3], [1], [10]}$. No subset of these segments has its XOR equal to $0$.

在第一个例子中，$2$ 是最大值。若将数组划分为 ${[5], [5, 7, 2]}$，则仅包含第二段的子集的异或值为 $5 \oplus 7 \oplus 2 = 0$；而划分为 ${[5, 5], [7, 2]}$ 时，仅包含第一段的子集的异或值为 $5 \oplus 5 = 0$。然而，划分为 ${[5, 5, 7], [2]}$ 时，会产生如下子集：${[5, 5, 7]}$ 的异或值为 $7$，${[2]}$ 的异或值为 $2$，以及 ${[5, 5, 7], [2]}$ 的异或值为 $5 \oplus 5 \oplus 7 \oplus 2 = 5$。

我们再考察一种划分为 $3$ 段的情形：${[5], [5, 7], [2]}$。它将产生以下子集：

• ${[5]}$，异或值为 $5$；
• ${[5, 7]}$，异或值为 $2$；
• ${[5], [5, 7]}$，异或值为 $7$；
• ${[2]}$，异或值为 $2$；
• ${[5], [2]}$，异或值为 $7$；
• ${[5, 7], [2]}$，异或值为 $0$；
• ${[5], [5, 7], [2]}$，异或值为 $5$；

如你所见，子集 ${[5, 7], [2]}$ 的异或值为 $0$，这是不可接受的。你可以验证：对于其他任意划分为 $3$ 段或 $4$ 段的情形，总存在某个非空子集的异或值为 $0$。

第二个例子不存在满足条件的划分。

第三个例子中的数组可划分为 ${[3], [1], [10]}$。这些段的任意非空子集的异或值均不为 $0$。