#include <bits/stdc++.h>
#include <cstdlib>

using namespace std;
#define ll long long


int main(int argc, char** argv) {
    cin.sync_with_stdio(false);

    int n;
    cin >> n;
    cout << "hello";
    int temps[n];
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        temps[i] = temp;
    }
    int q;
    cin >> q;
    vector<pair<int, int> > queries;
    for (int i = 0; i < q; i++) {
        int startDay;
        int endDay;
        cin >> startDay;
        cin >> endDay;
        queries.push_back(make_pair(startDay, endDay));
    }
    int subMins[n][n];
    int subMaxs[n][n];
    for (int exp = 0; pow(2,exp) < n+0.5; exp++) {
        int len = pow(2,exp);
        int a = 0;
        int b = a+len-1;
        while (a < n) {
            if (b < n) {
                int minTemp = temps[a];
                int maxTemp = temps[a];
                for (int i = a; i <= b; a++) {
                    minTemp = min(minTemp, temps[i]);
                    maxTemp = max(maxTemp, temps[i]);
                }
                subMins[a][len] = minTemp;
                subMaxs[a][len] = maxTemp;
            }
        }
    }
    for (int i = 0; i < q; i++) {
        int a = queries.at(i).first;
        int b = queries.at(i).second;
        int len = abs(b-a+1);
        int partLen = (int) pow((int) log2(len),2);
        int intervalMin = min(subMins[a][partLen], subMins[a+len-partLen][partLen]);
        int intervalMax = max(subMaxs[a][partLen], subMaxs[a+len-partLen][partLen]);
        cout << intervalMin << " " << intervalMax << "\n";
    }
    return 0;
}