Stone Game II

Problem Description

Alice and Bob are playing a game with stones.

There are $n$ piles of stones, where the $i$-th pile initially contains $a_i$ stones.

They take turns performing one of the following operations, starting with Alice:

• Split a pile that contains an odd number of stones into two non-empty piles.
• Merge two piles that each contain an even number of stones into one pile.

The player who cannot make any move loses.

Assuming both Alice and Bob play optimally, who will win the game?

Input Format

The first line contains an integer $n$ ($1 \le n \le 10^6$).

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

Output Format

Output a single line containing either Alice or Bob, indicating the final winner.

Sample Input

2
2 2

Sample Output

Alice