Сізде мөлшері \(n\) болатын \(a\) жиымы және келесі түрдегі \(q\) сұраулар бар: әрбір сұрау \(l\) және \(r\) деген екі саны арқылы беріледі. Әрбір сұрау үшін келесі әрекеттерді жасау қажет:

1. \(a_l, a_{l + 1}, \cdots, a_r\) сандарының арасында жоқ ең кіші теріс емес бүтін санды табыңыз. Бұл сан осы аралықтың \(MEX\)-і деп аталады.

2. \(a_l, a_{l+1}, \cdots, a_r\) барлық сандарын алдыңғы қадамда табылған \(MEX\) мәнімен ауыстырыңыз.

Әрбір сұрау үшін сол аралықтың \(MEX\) мәнін шығару керексіз.

Input

Бірінші жолда бір бүтін сан \(n\) \((1 \le n \le 100,000)\) — жиым өлшемі беріледі.

Екінші жолда \(n\) бүтін сандар \(a_1, a_2, \cdots, a_n\)(\(0 \le a_i \le n\)) — жиым элементтері.

Үшінші жолда бір бүтін сан \(q\) \((1 \le q \le 100,000)\) — сұраулар саны.

Келесі \(q\) жолда екі бүтін сан \(l\) және \(r\) \((1 \le l \le r \le n)\) бар — сұрауларды сипаттайтын сандар.

Output

Әрбір сұрау үшін, сол сұраудың \(MEX\) мәнін бөлек жолда шығарыңыз.

Sample Input 1

5
0 0 0 0 0
15
2 5
1 4
3 4
2 5
3 5
4 5
1 5
1 4
2 4
1 3
3 3
2 4
3 4
3 3
1 5

Sample Output 1

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

Sample Input 2

15
0 0 1 0 1 2 0 1 2 3 0 1 2 3 4
5
1 1
1 3
1 6
1 10
1 15

Sample Output 2

1
2
3
4
5