アリスとボブがゲームをしています。 彼らは $n$ 個の石の山を持っており、$i$ 番目の山には $a_i$ 個 ($1 \le a_i \le n$) の石があります。 各プレイヤーはアリスから順番に、自分のターンが来るたびに、いずれかの山を選び、その山から 1 個以上 $x$ 個以下の石を取り除きます。 自分のターンで石を取ることができない（すべての山が空である）プレイヤーが負けとなります。 アリスとボブはまだ最終的な $x$ の値を決めていないため、両者が最適にプレイした場合、$1 \le x \le n$ のすべての $x$ について、どちらが勝つかを求めてほしいと頼まれました。

入力

入力の最初の行には、整数 $n$ ($1 \le n \le 500\,000$) が含まれます。これは山の数であり、山にある石の数の上限でもあります。 次の行には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) が含まれます。これは各山にある石の数です。

出力

$n$ 個の単語を出力してください。そのうち $i$ 番目の単語は、$x = i$ の場合に最適プレイの下でアリスが勝つなら "Alice"、そうでなければ "Bob" とします。

入出力例

入力 1

6
6 6 6 6 6 6

出力 1

Bob Bob Bob Bob Bob Bob

入力 2

4
1 2 3 4

出力 2

Bob Alice Bob Alice

入力 3

5
1 2 3 2 2

出力 3

Bob Alice Bob Bob Bob

注記

最初の例では、$x$ にかかわらず、ボブは対称的な動き（同じ数の石を持つ山に対して同じ動きをする）をすることができるため、どのターンにおいても必ず少なくとも 1 つの有効な手を持つことができます。