E. Easy Win
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

Alice and Bob are playing a game.

They have $$$n$$$ piles of stones, such that there are $$$a_i$$$ ($$$1 \leq a_i \leq 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 \leq x \leq n$$$.

Input

The first line of input contains one integer $$$n$$$ ($$$1 \leq n \leq 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, \ldots, a_n$$$ ($$$1 \leq a_i \leq 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
6
6 6 6 6 6 6
Output
Bob Bob Bob Bob Bob Bob
Input
4
1 2 3 4
Output
Bob Alice Bob Alice
Input
5
1 2 3 2 2
Output
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.