Alicja i Bob grają w grę. Mają oni $n$ stosów kamieni, przy czym w $i$-tym stosie znajduje się $a_i$ ($1 \le a_i \le n$) kamieni. W swojej turze każdy gracz, zaczynając od Alicji, wybiera dowolny stos i zabiera z niego co najmniej jeden, a co najwyżej $x$ kamieni. Gracz, który nie może wykonać ruchu w swojej turze (wszystkie stosy są puste), przegrywa. Alicja i Bob nie zdecydowali jeszcze o ostatecznej wartości $x$, więc poprosili cię o ustalenie, kto wygra, jeśli obaj gracze grają optymalnie dla wszystkich wartości $x$ takich, że $1 \le x \le n$.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 500\,000$): liczbę stosów oraz górną granicę liczby kamieni w stosach. Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$): liczbę kamieni w stosach.

Wyjście

Wypisz $n$ słów, gdzie $i$-te z nich to „Alice”, jeśli Alicja wygra przy optymalnej grze dla $x = i$, oraz „Bob” w przeciwnym przypadku.

Przykład

Wejście 1

6
6 6 6 6 6 6

Wyjście 1

Bob Bob Bob Bob Bob Bob

Wejście 2

4
1 2 3 4

Wyjście 2

Bob Alice Bob Alice

Wejście 3

5
1 2 3 2 2

Wyjście 3

Bob Alice Bob Bob Bob

Uwagi

W pierwszym przykładzie, niezależnie od $x$, Bob może wykonywać ruchy symetryczne (ten sam ruch na stosie z taką samą liczbą kamieni), więc w każdej turze z pewnością będzie miał dostępny co najmniej jeden ruch.