골드리치의 비밀 금고

메이플스토리에서 골드리치의 비밀 금고 이벤트가 진행 중이다. 이 이벤트에 참여하는 사람은 $1$ 이상 $300\,000$ 이하의 수 하나를 제출한다. 이 이벤트에는 단 한 명의 사람만 당첨될 수 있는데, 당첨되는 사람은 "제출된 수 중 다른 플레이어와 겹치지 않으면서, 가장 작은 번호를 제출한 사람"이다.

예를 들어, $10$ 명의 사람이 각각 $1, 1, 5, 7, 6, 6, 5, 8, 9, 10$을 제출했다고 하자.

• $1, 5, 6$을 $2$ 명이 제출했으므로, 당첨자로 뽑히지 못한다.
• 남은 수 중 가장 작은 $7$을 제출한 사람이 당첨자가 된다.

단, 모든 수가 두 번 이상 제출되었을 경우 당첨자가 없을 수도 있음에 유의하자.

$1$부터 $N$까지 번호가 붙어있는 사람 $N$ 명이 있다. $i$번 사람이 제출하는 수는 $A_i$이다. 이때, 다음과 같은 질의를 처리하는 프로그램을 작성하라.

• $l$ $r$ : $l$번 사람부터 $r$번 사람까지 이벤트에 참여할 때, 당첨되는 사람이 제출한 수를 출력한다.

입력 형식

첫 줄에 이벤트에 참여하는 사람의 수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 300\,000$)

그다음 줄에 각 사람이 제출하는 수를 나타내는 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 300\,000$)

그다음 줄에 질의의 수 $Q$가 주어진다. ($1 \le Q \le 300\,000$)

이어지는 $Q$ 개의 줄의 $i$ 번째 줄에는 질의를 의미하는 $l$과 $r$이 공백으로 구분되어 주어진다. ($1 \le l \le r \le N$)

출력 형식

$Q$ 개의 줄에 걸쳐 정답을 출력한다. 출력의 $i$ 번째 줄에 $i$ 번째 질의에 대한 답을 출력한다. 만약, 당첨되는 사람이 없으면 $0$을 출력한다.

예제

10
1 1 5 7 6 6 5 8 9 10
4
1 10
2 8
9 9
1 2

7
1
9
0

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설