#include<bits/stdc++.h>
using namespace std;

vector < long long > a;
pair < long long, long long > b[145151];
long long tree[400089];
long long v1, v2, n, i, t, k, j, w;

void input()
{
    cin >> n;
    a.push_back(0);
    for ( i = 1; i <= n; i++ )
    {
        cin >> v1;
        a.push_back(v1);
    }
    cin >> t;
}

void full_tree( long long v, long long l, long long r )
{
    if ( l == r )
    {
        tree[v] = a[l];
    }
    else
    {
        long long m = l + ( r - l ) / 2;
        full_tree( v * 2, l, m );
        full_tree( v * 2 + 1, m + 1, r );
        tree[v] = max(tree[v*2], tree[v*2+1]);
    }
}

int get_max(long long ql, long long qr, long long v, long long l, long long r)
{
    if ( ql <= l && r <= qr )
    {
        return tree[v];
    }
    if ( r < ql || l > qr )
    {
        return 0;
    }
    long long m = l + ( r - l ) / 2;
    return max( get_max(ql, qr, v*2, l, m), get_max(ql, qr, v*2+1, m+1, r) );
}

void output()
{
    for ( i = 1; i < 4*n; i++ )
    {
        cout << tree[i] << " ";
    }
}

int main()
{
    input();
    full_tree( 1, 1, n );
    for ( i = 1; i <= t; i++ )
    {
        cin >> b[i].first >> b[i].second;
    }
    for ( i = 1; i <= t; i++ )
    {
        w = 1;
        v1 = b[i].first;
        v2 = b[i].second;
        k = get_max(v1, v2, w, 1, n);
        cout << k << endl;
    }
    //output();
}
