#include <iostream>

#include <stdio.h>

#include <math.h>

#include <algorithm>

#include <cstdio>

using namespace std;

const int maxn = 5e4 + 10;

int N, M;

int a[maxn];

int maxx[maxn][30], minn[maxn][30];

void RMQ(int num) {

    for(int i = 1; i <= N; i ++) {

        maxx[i][0] = a[i];

        minn[i][0] = a[i];

    }

    for(int j = 1; j < 23; j ++) {

        for(int i = 1; i <= num; i ++) {

            if(i + (1 << j) - 1<= num) {

                maxx[i][j] = max(maxx[i][j - 1], maxx[i + (1 << (j - 1))][j - 1]);

                minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]);

            }

        }

    }

}

int QueryMax(int l, int r) {

    int k = (int)(log(r - l + 1) / log(2.0));

    int ans = max(maxx[l][k], maxx[r - (1 << k) + 1][k]);

    return ans;

}

int QueryMin(int l, int r) {

    int k = (int)(log(r - l + 1) / log(2.0));

    int ans = min(minn[l][k], minn[r - (1 << k) + 1][k]);

    return ans;

}

int main() {

    scanf("%d%d", &N, &M);

    for(int i = 1; i <= N; i ++)

        scanf("%d", &a[i]);

    RMQ(N);

    while(M --) {

        int st, en;

        scanf("%d%d", &st, &en);

        int maxnum = QueryMax(st, en);

        int minnum = QueryMin(st, en);

        printf("%d %d\n", maxnum, minnum);

    }

    return 0;

}