긴 게임

Alice와 Bob은 1부터 n까지의 정수로 이루어진 순열 p = (p1, p2, ..., pn)로 긴 게임을 한다. 순열은 하나의 띠에 적혀 있다. Alice가 먼저 차례를 가지며, 이후 두 사람은 번갈아 차례를 가진다. 차례를 가진 사람이 아무 수를 두지 못하면 진다.

i번째 차례에서 플레이어는 i개의 띠 중 하나를 고르고, 그 길이를 m ≥ 2라 하자. 그런 다음 정수 k (1 ≤ k < m)를 골라 고른 띠를 길이 k와 m - k의 두 새 띠로 자른다. 여기서 k는 고른 띠의 원소 중 첫 번째 조각의 마지막 원소가 되는 원소의 위치를 뜻하므로, (k + 1)번째 원소는 두 번째 조각의 처음으로 간다. 다만 자른 뒤 다음 조건이 성립해야 한다. 남아 있는 모든 띠 중에서 원소들이 역전을 하나 이상 이루는 띠가 적어도 하나 있어야 한다. 즉, i < j이면서 pi > pj인 위치 쌍 i, j가 존재해야 한다. 이 조건이 성립하지 않으면 그 수는 불법이며 둘 수 없다. 새로 만들어진 띠에서 원소의 순서는 바뀌지 않으며, 플레이어는 어떤 띠의 원소도 뒤집거나 교환할 수 없다.

n개의 정수로 이루어진 순열 p가 주어질 때, 두 플레이어가 최적으로 플레이하면 누가 이기는지 구하시오.

첫째 줄에 순열의 길이 n (2 ≤ n ≤ 105)이 주어진다.

둘째 줄에 n개의 정수 p1, p2, ..., pn (1 ≤ pi ≤ n, 모든 pi는 서로 다름)이 공백으로 구분되어 주어진다. 이는 순열 자체이다.

첫 번째 플레이어가 이기면 “Alice”를, 그렇지 않으면 “Bob”을 한 단어로 출력한다.