1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define INF 0x7fffffff
 7 int maxv=-INF;
 8 struct node
 9 {
10     int l,r;
11     int maxv;
12     int mid()
13     {
14         return (l+r)/2;
15     }
16 }tree[800020];
17 void buildtree(int root,int l,int r)
18 {
19     tree[root].l=l;
20     tree[root].r=r;
21     tree[root].maxv=-INF;
22     if(l!=r)
23     {
24         buildtree(2*root+1,l,(l+r)/2);
25         buildtree(2*root+2,(l+r)/2+1,r);
26     }
27 }
28 void insert(int root,int i,int v)
29 {
30     if(tree[root].l==tree[root].r)
31     {
32         tree[root].maxv=v;
33         return;
34     }
35     tree[root].maxv=max(tree[root].maxv,v);
36     if(i<=tree[root].mid())
37         insert(root*2+1,i,v);
38     else
39         insert(root*2+2,i,v);
40 }
41 void query(int root,int s,int e)
42 {
43     if(maxv>=tree[root].maxv)
44         return;
45     if(tree[root].l==s&&tree[root].r==e)
46     {
47         maxv=max(tree[root].maxv,maxv);
48         return;
49     }
50     if(e<=tree[root].mid())
51         query(2*root+1,s,e);
52     else if(s>tree[root].mid())
53         query(2*root+2,s,e);
54     else
55     {
56         query(2*root+1,s,tree[root].mid());
57         query(2*root+2,tree[root].mid()+1,e);
58     }
59 }
60 int main()
61 {
62     int T,n,m,i,j;
63     cin>>T;
64     while(T--)
65     {
66         cin>>n;
67         buildtree(0,1,n);
68         for(i=1;i<=n;i++)
69         {
70             int h;
71             cin>>h;
72             insert(0,i,h);
73         }
74         cin>>m;
75         for(i=0;i<m;i++)
76         {
77             int s,e;
78             cin>>s>>e;
79             maxv=-INF;
80             query(0,s,e);
81             printf("%d\n",maxv);
82         }
83     }
84     return 0;
85 }