Alice and Bob are playing a game.

They have $n$ piles of stones, such that there are $a_i$ ($1 \le a_i \le n$) stones in the $i$-th pile.

During his/her turn, each player, starting from Alice, will pick any pile and take at least one and at most $x$ stones from it.

The player that can’t make a move on his/her turn (all piles are empty) loses.

Alice and Bob still have not decided the final value of $x$, so they have asked you to find out who will win if both players play optimally for all values of $x$, such that $1 \le x \le n$.

Input

The first line of input contains one integer $n$ ($1 \le n \le 500\,000$): the number of piles and the upper bound on the number of stones in piles.

The next line contains $n$ integers, $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$): the number of stones in piles.

Output

Print $n$ words, where the $i$-th of them is "Alice" if Alice will win under optimal play for $i = x$, and "Bob" otherwise.

Examples

Input 1

6
6 6 6 6 6 6

Output 1

Bob Bob Bob Bob Bob Bob

Input 2

4
1 2 3 4

Output 2

Bob Alice Bob Alice

Input 3

5
1 2 3 2 2

Output 3

Bob Alice Bob Bob Bob

Note

In the first example, independently on $x$, Bob may do symmetrical moves (the same move on the pile with the same number of stones), so on each turn, he definitely will have at least one available move.