众所周知，TiChuot97 是史上最伟大的职业玩家之一。和其他伟大的玩家一样，他热爱游戏，尤其是尼姆游戏（nim games）。今天，他刚发现了一款在线尼姆游戏——Egma。和其它尼姆游戏一样，精通 Egma 需要具备计算 mex 值的能力。TiChuot97 明白，就像他精通的其他数百万款游戏一样，Egma 也需要练习。这时，他的好朋友 tourist 来帮忙了。

tourist 为 TiChuot97 的练习准备了一套训练题。最初，TiChuot97 得到一个大小为 $n$ 的非负整数数组 $a_1, a_2, \dots, a_n$。然后，tourist 会给出 $q$ 个询问，每个询问包含两个数字 $l, r$ ($1 \le l \le r \le n$)，要求计算 $\{a_l, a_{l+1}, \dots, a_r\}$ 的 mex 值。当然，TiChuot97 轻松完成了这项训练。然而，他认为这个挑战不仅能提高他的 mex 计算能力，还能提高他的编程能力。你也想尝试一下这个挑战吗？

说明：非负整数集合的 mex 值定义为不属于该集合的最小非负整数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)，表示初始数组的长度。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。第三行包含一个整数 $q$ ($1 \le q \le 5 \times 10^5$)，表示询问次数。接下来的 $q$ 行，每行包含一对 $l, r$ ($1 \le l \le r \le n$)，描述一个询问。

输出格式

对于每个询问，输出一行该询问的答案。

样例

输入 1

5
1 2 3 0 5
2
1 3
1 4

输出 1

0
4