← 返回题目列表

AtCoder · cf16_exhibition_final_c

C. 作弊尼姆

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

一只猎豹和一个骗子要玩 Nim 游戏。 在这个游戏中他们使用 N 成堆的石头。 最初的 i- 第堆包含 a_i 石头。 玩家轮流进行,猎豹先玩。 在每一回合中,玩家选择其中一堆,并从该堆中取出一颗或多颗石头。 无法采取行动的玩家就输了。

然而,在游戏开始之前,作弊者想要作一点小作弊,以确保无论猎豹如何走动,他都能获胜。 作弊者从每一堆石头中取出零个或一个石头并在比赛前吃掉。 如果有多种方法可以保证他获胜,他想尽量减少吃掉的石头数量。

计算作弊者将吃掉的石头数量。 如果作弊者即使作弊也无法赢得比赛,则打印 -1 代替。

约束

  • 1 ≤ N ≤ 10^5
  • 2 ≤ a_i ≤ 10^9

输入

输入由标准输入按以下格式给出:

N
a_1
:
a_N

输出

打印答案。


样本输入 1

3
2
3
4

示例输出 1

3

作弊者赢得比赛的唯一方法就是从所有堆中取出石头并吃掉它们。


示例输入 2

3
100
100
100

示例输出 2

-1