You are given an array of N integers. Two players, Alice and Bob, play a game. They take turns removing exactly one element from the array until only two elements remain. Alice goes first.
Alice wins if the sum of the two remaining elements is even. Bob wins if the sum of the two remaining elements is odd.
Your task is to determine which player will win the game, assuming both players play optimally.
Input
The first line contains a single integer N (3 \le N \le 2 \cdot 10^5).
The second line contains N integers a_1, a_2, \dots, a_N (1 \le a_i \le 10^9).
Output
Print "Alice" (without quotes) if Alice wins the game, and "Bob" (without quotes) if Bob wins the game.
Examples
| standard input | standard output |
|---|
| 3
1 2 3
| Alice
|
| 4
1 2 2 2
| Alice
|
| 4
1 1 2 2
| Bob
|