410777: GYM104101 J Simple Game
Description
Alice and Bob are playing a game on a sequence $$$a_1,a_2 \cdots a_n$$$ of length $$$n$$$. They move in turns, and Alice moves first.
At each player's turn, they should select an integer and remove it from the sequence. The game ends when there is no integer left in the sequence.
Assume the sum of integers selected by Alice is $$$S_1$$$, and the sum of integers selected by Bob is $$$S_2$$$.
If the difference between $$$S_1$$$ and $$$S_2\ (ie.\lvert S_1 - S_2 \rvert)$$$ is odd, Alice wins; Otherwise, Bob wins.
Your task is to determine who will win the game if both players play optimally.
InputThe first line contains an integer $$$n\ (1 \le n \le 10^6)$$$, indicating the length of the sequence.
The second line contains $$$n$$$ integers $$$a_1,a_2 \cdots a_n\ (1 \le a_i \le 10^9)$$$, indicating the elements of the sequence.
OutputThe first line output "Alice" (without quotes) if Alice wins and "Bob" (without quotes) otherwise. It is obvious that there is no draw.
ExamplesInput5 1 2 3 4 5Output
AliceInput
2 2 4Output
Bob