19300번 - Game of Sorting 다국어

Alice and Bob have invented a new game to play. First, they get a sequence. And then they take turns to make the following moves. During each move, the play will choose either the first element of the sequence or the last element, and remove the chosen element. The player who makes the sequence nondecreasing or nonincreasing wins. If the initial sequence is a nondecreasing or nonincreasing sequence, Bob wins the game.

The winter vacation is boring, so the kids want to play this game many times. Initially, they have a sequence of length $n$: $a_1, a_2, \ldots, a_n$. Alice realized that if they start the game after removing some of the first elements of the sequence and some of its last elements, you can get completely different results.

Alice and Bob played the game $Q$ times in total. The question is who will finally win each game if both players play optimally. Remember that Alice always moves first.

The first line contains an integer $n$, the length of the initial sequence ($3 \le n \le 10^6$).

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$: the sequence itself ($1 \le a_i \le 10^9$).

The third line contains an integer $Q$ ($1 \le Q \le 10^6$).

The $i$-th of the following $Q$ lines contains integers $L_i$ and $R_i$ ($1 \le L_{i} \le R_{i} \le n$). It means that the initial sequence of $i$-th game is $a_{L_i}, a_{L_i + 1}, \ldots, a_{R_i}$.

Print $Q$ lines with the winner's name, one for each query.