给定一个整数数组 $$$a_1, a_2, \dots, a_n$$$。
您的任务是将数组划分为最大数量的段,方式如下:
- 每个元素恰好包含在一个段中;
- 每个段至少包含一个元素;
- 不存在段的非空子集,使得它们中的数字的按位异或等于 $$$0$$$。
打印数组可以分为的最大段数。如果不存在合适的划分,则打印 -1。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的大小。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。
输出
打印在遵循给定约束的情况下数组可以分为的最大段数。如果不存在合适的划分,则打印 -1。
示例
输入 #1
4 5 5 7 2
输出 #1
2
输入 #2
3 1 2 3
输出 #2
-1
输入 #3
3 3 1 10
输出 #3
3
注意
在第一个示例中,$$$2$$$ 是最大数量。如果将数组分为$$$\{[5], [5, 7, 2]\}$$$,则仅第二段的子集的异或值为$$$5 \oplus 7 \oplus 2 = 0$$$。 $$$\{[5, 5], [7, 2]\}$$$ 仅第一段的子集值为 $$$5 \oplus 5 = 0$$$。然而,$$$\{[5, 5, 7], [2]\}$$$ 将导致 XOR $$$7$$$ 的子集 $$$\{[5, 5, 7]\}$$$,XOR $$$2$$$ 的 $$$\{[2]\}$$$ 和 XOR $$$5 \oplus 的 $$$\{[5, 5, 7], [2]\}$$$ 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$$$ XOR 的非空子集始终存在。
第二个示例没有合适的划分。
第三个示例数组可以分为$$$\{[3], [1], [10]\}$$$。这些段的子集的 XOR 都不等于 $$$0$$$。