수열 정렬 게임

Alice와 Bob은 새로운 게임을 만들었다. 먼저 수열을 받는다. 그다음 두 사람이 번갈아 한 번씩 움직인다. 각 차례에서 플레이어는 수열의 첫 번째 원소나 마지막 원소 중 하나를 골라 제거한다. 수열을 비내림차순 또는 비오름차순으로 만든 플레이어가 이긴다. 처음 수열이 이미 비내림차순 또는 비오름차순이면 Bob이 이긴다.

겨울 방학이 지루해서 아이들은 이 게임을 여러 번 하고 싶어 한다. 처음에 길이가 $n$인 수열 $a_1, a_2, \ldots, a_n$이 있다. Alice는 수열의 앞부분 일부와 뒷부분 일부를 제거한 뒤 게임을 시작하면 결과가 완전히 달라질 수 있다는 것을 알아냈다.

Alice와 Bob은 이 게임을 총 $Q$번 했다. 두 플레이어가 최적으로 행동할 때 각 게임의 승자를 구하라. Alice가 항상 먼저 움직인다.

첫 줄에 초기 수열의 길이 $n$이 주어진다 ($3 \le n \le 10^6$).

둘째 줄에 공백으로 구분된 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^9$).

셋째 줄에 $Q$가 주어진다 ($1 \le Q \le 10^6$).

이어지는 $Q$개의 줄마다 $L_i$와 $R_i$가 주어진다 ($1 \le L_i \le R_i \le n$). $i$번째 게임은 $a_{L_i}, a_{L_i+1}, \ldots, a_{R_i}$ 수열에서 시작한다.

$Q$개의 줄을 출력한다. 각 줄에는 해당 게임의 승자 이름을 쓴다.