Well, you can't imagine what kind of a legend we could create for this problem. We wanted to create a long story on three pages with lots of unnecessary information. Another idea was to bind our task to some fictional situation, where two players play the game and they someway already know Grundy values for their positions... But then we remembered how much we dislike such type of legends on contests, that have nothing common with the task, so all the spam in this statement ends in this paragraph.
(minimum excludant) of a finite set of nonnegative integers S is the minimal non-negative integer 
.
You are given a 1-indexed array A consisting of N nonnegative integers, and also Q queries (Li, Ri). For each query (Li, Ri), find a for the subsegment of this array with indices from Li to Ri inclusive.
The first line contains N, the size of the array (1 ≤ N ≤ 1 000 000).
The second line contains N integers Ai (0 ≤ Ai ≤ 1 000 000) separated by spaces.
The third line contains Q, the number of queries you need to process (1 ≤ Q ≤ 1 000 000).
The following Q lines contain the description of the queries in the form Li Ri (1 ≤ Li ≤ Ri ≤ N).
For each query according to their order in the input, print the -value of the corresponding subsegment on a separate line.
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
1
1
3
3
4
1
0
