3197. 石子游戏

【题目描述】

Alex和Bob在玩游戏。游戏规则如下：桌上有 n 堆石子，每堆石子有 ai 个，Alex和Bob轮流操作，Bob做第一次操作。每次操作时，操作者可以选择一堆石子，并从这堆石子中取出至少一个石子。最后无法操作的人输。可以发现这就是一个Nim游戏。

Alex发现他并不能赢，于是他决定删去若干堆石子（可以不删，也可以全删，删去一堆石子可以理解为将这堆石子的个数变为 0 个），使得在双方都采用最优决策的情况下，Alex能赢。同时Alex希望留下尽量多的堆数，你需要求出最多可能留下的堆数。

【输入格式】

第一行一个整数 n 表示石子堆数。

第二行 n 个整数，分别表示 a1; a2; a3; ... an。

【输出格式】

一行 1 个整数，表示最多能剩下多少堆石子。

【样例输入】

8
1 9 2 6 0 8 1 7

【样例输出】

7

【提示】

40%数据 n*maxai ≤ 10000000

100%数据 1 ≤ n ≤ 500000; 0 ≤ ai ≤ 500000。