406779: GYM102538 E Easy Win

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

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.

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

6
6 6 6 6 6 6

Bob Bob Bob Bob Bob Bob 

4
1 2 3 4

Bob Alice Bob Alice 

5
1 2 3 2 2

Bob Alice Bob Bob Bob 

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.