/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
石の山が N 個あり，i 番目 (1 \leq i \leq N) の山には A_i 個の石が積まれています．
あなたは今から正整数 k を選びます． その後，Alice と Bob がこの山を使って以下のようなゲームを行います．
- Alice から始めて両者は交互に手番をプレイする．
- 各手番では，プレイヤーは空でない山を一つ選び，その山から 1 個以上 k 個以下の好きな個数の石を取り除く．
自分の手番で操作が行えなくなった人が負けで，負けなかった人が勝ちです．
あなたは正整数 k を選ぶとき，Alice に必勝法が存在するようにしたいです． そのような k が存在するか判定してください． 存在する場合は，そのような k の最大値が存在するか判定してください． 最大値が存在する場合は，その値を答えてください．
制約
- 1 \leq N \leq 250000
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \cdots A_N
出力
Alice に必勝法が存在するような k が存在しない場合，0 を出力せよ．
Alice に必勝法が存在するような k が存在するが，その最大値が存在しない場合，-1 を出力せよ．
Alice に必勝法が存在するような k が存在し，その最大値も存在する場合，その値を出力せよ．
入力例 1
3 1 2 3
出力例 1
2
例えば，k=2 とすると Alice に必勝法が存在します． 3 \leq k を選んだ場合は Alice に必勝法が存在しないので，k=2 が答えです．
入力例 2
4 1 2 3 4
出力例 2
-1
例えば，すべての k=100,200,300,\cdots に対して Alice に必勝法が存在します． よって k の最大値は存在しないため，-1 を出力します．
入力例 3
2 100 100
出力例 3
0
どのような k を選んでも Alice に必勝法は存在しません． よって 0 を出力します．
Score : 400 points
Problem Statement
There are N piles of stones, and the i-th pile (1 \leq i \leq N) has A_i stones.
You will choose a positive integer k. Then, Alice and Bob will play a game with these piles as follows.
- Starting with Alice, the players take turns to play.
- In each turn, the player must choose a non-empty pile and remove from it some number of stones between 1 and k, inclusive.
The person who cannot make a move on their turn loses, and the other person wins.
You want to choose a positive integer k for which there is a winning strategy for Alice. Determine if such a k exists. If it exists, determine if there is a maximum value for such k. If the maximum value exists, provide that value.
Constraints
- 1 \leq N \leq 250000
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
If there is no k for which Alice has a winning strategy, print 0.
If there is a k for which Alice has a winning strategy, and there is no maximum value for such k, print -1.
If there is a k for which Alice has a winning strategy, and there is a maximum value for such k, print that value.
Sample Input 1
3 1 2 3
Sample Output 1
2
For example, if k=2, Alice has a winning strategy. If k \geq 3, Alice has no winning strategy, so the answer is k=2.
Sample Input 2
4 1 2 3 4
Sample Output 2
-1
For example, Alice has winning strategies for all k=100,200,300,\cdots. Thus, there is no maximum value for k, so print -1.
Sample Input 3
2 100 100
Sample Output 3
0
No matter what k is chosen, Alice has no winning strategy. Thus, print 0.