#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
    int l;
    int r;
} query;

int** preprocess(int *input, int inputLength) {
    int i, j, lg = log(inputLength);
    
    int* *prepMat = (int**) malloc((inputLength + 1) * sizeof(int*));
    for (i = 1; i <= inputLength; i++) {
        prepMat[i] = (int*) malloc((lg + 1) * sizeof(int)); 
    }

    for (i = 1; i <= inputLength; i++) {
        prepMat[i][0] = i;
    }

    for (j = 1; 1 << j <= inputLength; j++) {
        for (i = 1; i + (1 << j) - 1 <= inputLength; i++) {
            if (input[prepMat[i][j-1]] < input[prepMat[i + (1 << (j - 1))][j - 1]]) {
                prepMat[i][j] = prepMat[i][j - 1];
            } else {
                prepMat[i][j] = prepMat[i + (1 << (j - 1))][j - 1];
            }
        }
    }

    return prepMat;
}

int* rmq2(int *input, int inputLength, query *queries, int queriesLength) {
    int *answer = (int*) malloc(queriesLength * sizeof(int));
    int* *prepMat = preprocess(input, inputLength);

    int i;
    for (i = 0; i < queriesLength; i++) {
        int l = queries[i].l;
        int r = queries[i].r;
        int lg = log(r - l + 1);
        if (input[prepMat[l][lg]] < input[prepMat[r - (1 << lg) + 1][lg]]) {
            answer[i] = prepMat[l][lg];
        } else {
            answer[i] = prepMat[r - (1 << lg) + 1][lg];
        }
    }

    for (i = 0; i < inputLength; i++) {
        free(prepMat[i]);
    }
    free(prepMat);

    return answer;
}

int main() {
    FILE *in = fopen("rmq.in", "r");
    FILE *out = fopen("rmq.out", "w");

    int N, M, x, y, i;
    fscanf(in, "%d %d", &N, &M);

    int *input = (int*) malloc((N +1 )* sizeof(int));
    query *queries = (query*) malloc(M * sizeof(query));

    for (i = 1; i <= N; i++) {
        fscanf(in, "%d", &input[i]);
    }

    for (i = 0; i < M; i++) {
        fscanf(in, "%d %d", &queries[i].l, &queries[i].r);
    }

    int *answer = rmq2(input, N, queries, M);

    for (i = 0; i < M; i++) {
        fprintf(out, "%d\n", input[answer[i]]);
    }

    free(input);
    free(queries);
    free(answer);
    fclose(in);
    fclose(out);

    return 0;
}