Alice 和 Bob 发明了一个新游戏。首先，他们得到一个序列。然后他们轮流进行以下操作：在每一轮中，玩家可以选择序列的第一个元素或最后一个元素，并将其移除。使序列变为非递减或非递增的玩家获胜。如果初始序列本身就是非递减或非递增的，则 Bob 获胜。

寒假很无聊，所以孩子们想玩很多次这个游戏。最初，他们有一个长度为 $n$ 的序列：$a_1, a_2, \dots, a_n$。Alice 意识到，如果他们在移除序列开头的一些元素和结尾的一些元素后开始游戏，可能会得到完全不同的结果。

Alice 和 Bob 总共玩了 $Q$ 次游戏。问题是，如果双方都采取最优策略，谁最终会赢得每一场游戏？请记住，Alice 总是先手。

输入格式

第一行包含一个整数 $n$，表示初始序列的长度 ($3 \le n \le 10^6$)。 第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$，即序列本身 ($1 \le a_i \le 10^9$)。 第三行包含一个整数 $Q$ ($1 \le Q \le 10^6$)。 接下来的 $Q$ 行中，第 $i$ 行包含整数 $L_i$ 和 $R_i$ ($1 \le L_i \le R_i \le n$)。这意味着第 $i$ 场游戏的初始序列为 $a_{L_i}, a_{L_i+1}, \dots, a_{R_i}$。

输出格式

输出 $Q$ 行，每行包含获胜者的名字。

样例

样例输入 1

4
1 5 3 4
3
1 2
1 3
1 4

样例输出 1

Bob
Alice
Bob