一道有意思的线段树题目，维护一个pair值（下一个元素的位置,权值）对其维护最大值（就是影响越持久）
把问题离线处理，按照问题的右端点排序，这样就能满足单调性
输出的时候一定要判断一下first的值是否符合要求
注意：

  • 这棵线段树维护的是最大值，不管是修改还是查询都需要取max
  • 如果没有nxt，数组的值要赋值为n+1

F. One Occurrence

time limit per test:3 seconds
memory limit per test:768 megabytes
input:standard input
output:standard output

You are given an array a consisting of n integers, and q queries to it. i-th query is denoted by two integers li and ri. For each query, you have to find any integer that occurs exactly once in the subarray of a from index li to index ri (a subarray is a contiguous subsegment of an array). For example, if a=[1,1,2,3,2,4], then for query (li=2,ri=6) the subarray we are interested in is [1,2,3,2,4], and possible answers are 1, 3 and 4; for query (li=1,ri=2) the subarray we are interested in is [1,1], and there is no such element that occurs exactly once.

Can you answer all of the queries?

Input

The first line contains one integer n (1≤n≤5⋅105).

The second line contains n integers a1,a2,…,an (1≤ai≤5⋅105).

The third line contains one integer q (1≤q≤5⋅105).

Then q lines follow, i-th line containing two integers li and ri representing i-th query (1≤li≤ri≤n).

Output

Answer the queries as follows:

If there is no integer such that it occurs in the subarray from index li to index ri exactly once, print 0. Otherwise print any such integer.

Example

input

1
2
3
4
5
6
1 1 2 3 2 4
2
2 6
1 2

output

1
2
4
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3F3F3F3F
using namespace std;
typedef pair<int,int>pii;
struct Node
{
	int L,R,id;
}b[500005];
struct Tree
{
	int L,R;
	pii val;
}T[2000005];
int a[500005],pre[500005],nxt[500005],h[500005],ans[500005];
inline void Modify(int L,int R,pii val,int v)
{
	if(L>T[v].R||R<T[v].L)return;
	if(L<=T[v].L&&R>=T[v].R)
	{
		T[v].val=max(T[v].val,val);return;
	}
	Modify(L,R,val,v<<1);
	Modify(L,R,val,(v<<1)|1);
	return;
}
inline pii Query(int x,int v)
{
	if(x>T[v].R||x<T[v].L)return make_pair(-inf,0);
	if(T[v].L==T[v].R)return T[v].val;
	return max(T[v].val,max(Query(x,v<<1),Query(x,(v<<1)|1)));
}
inline void Build(int L,int R,int v)
{
	T[v].L=L;T[v].R=R;
	T[v].val=make_pair(-inf,0);
	if(L==R)return;
	int mid=(L+R)>>1;
	Build(L,mid,v<<1);
	Build(mid+1,R,(v<<1)|1);
	return;
}
inline bool cmp(const Node& a,const Node& b)
{
	return a.R<b.R;
}
int main(void)
{
	int i,j=1,n,m;
	scanf("%d",&n);
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	for(i=1;i<=n;++i)
	{
		if(!h[a[i]])pre[i]=0;
		else pre[i]=h[a[i]];
		h[a[i]]=i;
	}
	memset(h,0,sizeof(h));
	for(i=n;i>=1;--i)
	{
		if(!h[a[i]])nxt[i]=n+1;
		else nxt[i]=h[a[i]];
		h[a[i]]=i;
	}
	scanf("%d",&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&b[i].L,&b[i].R);
		b[i].id=i;
	}
	sort(b+1,b+m+1,cmp);
	Build(1,n+1,1);
	for(i=1;i<=m;++i)
	{
		while(j<=b[i].R)Modify(pre[j]+1,j,make_pair(nxt[j],a[j]),1),++j;
		pii tmp=Query(b[i].L,1);
		if(tmp.first>=j)ans[b[i].id]=tmp.second;
	}
	for(i=1;i<=m;++i)printf("%d\n",ans[i]);
	return 0;
}