Description

\(mex\)是一个作用在集合上的函数，\(mex(S)\)表示不在集合\(S\)中的最小非负整数。
现在我们有一个长度为\(n\)的序列和\(Q\)个询问，每个询问查询序列中一段区间内的数组成的集合的\(mex\)值。

Format

Input

每个测试点仅包含一组输入数据。
第一行一个正整数\(n(n<=1000000)\)。
接下来一行\(n\)个整数，第\(i\)个整数\(a_i(0<=a_i<=1000000)\)表示序列的第\(i\)个数。
接下来一行一个正整数\(Q(Q<=1000000)\)。
接下来\(Q\)行，每行两个整数\(l,r(1<=l<=r<=n)\)，表示查询序列第\(l\)个数到第\(r\)个数所组成集合的\(mex\)值。

Output

依照输入顺序，对于每组询问输出一行一个整数表示答案。

Sample 1

Input

10
2 0 1 3 0 0 2 4 7 1
7
1 2
5 6
5 10
1 3
1 5
6 6
7 8

Output

1
1
3
3
4
1
0

Limitation

4s, 1GB for each test case.

Source

Vijos Original