410777: GYM104101 J Simple Game

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.

The 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.

The first line output "Alice" (without quotes) if Alice wins and "Bob" (without quotes) otherwise. It is obvious that there is no draw.

5
1 2 3 4 5

Alice

2
2 4

Bob