#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <string>
using namespace std;

class Mo{
    #define MAXN 1000004
    #define MAGIC 1000
    int data[MAXN];
    int maxes[MAGIC+233];
    int n;
public:
    Mo(int maxn){
        n = maxn;
    }
    void getData(){
        for(int i = 0; i <= n; i++)
            scanf("%d", data+i);
    }
    void moInit(){
        for(int i = 0; i <= n; i++)
            if(i % MAGIC == 0 || data[i] > maxes[i/MAGIC])
                maxes[i/MAGIC] = data[i];
    }
    int query(int l, int r){
        int ret = data[l];
        for(int j = l; j <= r;){
            if(j % MAGIC == 0 && j + MAGIC - 1 <= r){   
                if(maxes[j/MAGIC] > ret)ret = maxes[j/MAGIC];
                j += MAGIC;
            }else{
                if(data[j] > ret)ret = data[j];
                j++;
            }            
        }
        return ret;
    }
};

int main(){
    freopen("climb.in", "r", stdin);
    freopen("climb.out", "w", stdout);
    int n, q;
    scanf("%d", &n);
    Mo *solver = new Mo(n);
    solver -> getData();
    solver -> moInit();
    scanf("%d", &q);
    while(q--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", solver -> query(a, b));
    }
    delete solver;   
    return 0;
}