题目描述

有一个长度为$\red{n}$的序列$\red{a_1,...,a_n}$。

如果序列的长度大于$\red{1,}$那么你就能进行操作，每次操作可以选择两个相邻的数$\red{a_i,a_{i+1}}$合并，得到$\red{-}$一个 新的数$\red{a_i}$田$\red{a{i+1} （}$"田"表示异或），每次操作都会使序列的长度减少$\red{1}$。 例如对将序列$\red{[8,3,5, 7,1]}$中的第$\red{2}$ 个和第$\red{3}$个数进行合并，会得到新序列$\red{[8,6,7,1], }$并可以进行下一轮操作。

你需要进行若干次操作（可能是$\red{0}$次）,使得最终序列任意子区间的异或和不为$\red{0}$。子区间的定义为连续 的一段数$\red{[a_l,a_{1+1},... ,a_r] (l≤}$$\red{r)}$。求满足条件的最终序列的最长长度。

输入格式

第一行一个正整数$\red{n,}$表示序列长度。

第二行$\red{n}$个正整数$\red{a_1,... ,a_n}$，表示序列。

输出格式

一个整数，满足条件的最终序列的最长长度。如果不存在这样的序列则输出"$\red{-1}$" （不含引号）。

样例

输入样例

4
5 5 7 2

输出样例

2

提示

一种方案是先选择$\red{a_1,a_2}$合并，得到$\red{[0,7,2]}$，再选择前两个数合并，得到$\red{[7,2]}$。不存在方案使得最终序列长度为$\red{3}$或$\red{4}$。

对于所有测试点，$\red{1≤n≤10^5, 0≤a_i≤10^9}$。