#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<limits.h>
#define ll long long
#pragma warning(disable : 4996)

using namespace std;
#define N 400010

ll a[N];//原来的值
struct pp
{
ll l, r;
}fp[N];//区间
ll ss[N];//查询节点
ll maxn[N];//区间最大值
int main()
{
//freopen("in.txt", "r", stdin);
ll n;
for (int i = 0; i < N; i++)
ss[i] = LLONG_MIN;
scanf("%lld", &n);
for (ll i = 1; i <= n; i++)
scanf("%lld", &a[i]);
ll m;
ll cnt = 0;
scanf("%lld", &m);
for (ll i = 1; i <= m; i++)
{
scanf("%lld%lld", &fp[i].l, &fp[i].r);
ss[cnt++] = fp[i].l;
ss[cnt++] = fp[i].r;
}
sort(ss, ss + cnt);
ll en = unique(ss, ss + cnt) - ss;
for (ll i = 0; i < en - 1; i++)
for (ll j = ss[i]; j <= ss[i + 1]; j++)
if (a[j] > maxn[i])
maxn[i] = a[j];
for (ll i = 1; i <= m; i++)
{
ll l, r;
l = lower_bound(ss, ss + en, fp[i].l) - ss;
r = lower_bound(ss, ss + en, fp[i].r) - ss;
if (l > en)
l = 1;
if (r > en)
r = en;
if (l > r)
swap(l, r);

ll ans = maxn[l];
for (ll j = l; j < r; j++)
{
ans = max(ans, maxn[j]);
}
printf("%lld\n", ans);
}
}