#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>

using std::priority_queue;
using std::vector;

#define Smerenie 1000000
#define Nadejde 100000

/** Aici este o schita a algoritmului lui Mo! **/

typedef struct {
  int l, r, init;
  short int loc;
} cell;

int N, M;
int sum;
int val[Nadejde + 1];
char seen[Nadejde + 1];
int answer[Smerenie + 1];
cell query[Smerenie + 1];

typedef struct {
  bool operator()(const int &X, const int &Y) {
    return val[X] > val[Y];
  }
} minHeap;

priority_queue <int, vector <int>, minHeap> heap;

/** Cmp-ul pentru sortarea din algoritmul lui Mo. **/
int cmp(cell &X, cell &Y) {
  return ((X.loc < Y.loc) || ((X.loc == Y.loc) && (X.r > Y.r)));
}

/** Sortarea lui Mo. **/
void sort(int begin, int end) {
  int b = begin, e = end;
  cell tmp, pivot = query[(b + e) >> 1];

  while (b <= e) {
    while (cmp(query[b], pivot)) {
      b++;
    }
    while (cmp(query[e], pivot)) {
      e--;
    }
    if (b <= e) {
      tmp = query[b];
      query[b++] = query[e];
      query[e--] = tmp;
    }
  }
  if (begin < e) {
    sort(begin, e);
  }
  if (b < end) {
    sort(b, end);
  }
}

/** Functii stas: **/

/** Inserare. **/
void insert(int pos) {
  heap.push(pos);
  seen[pos] = 1;
}

/** Stergere. **/
void erase(int pos) {
  seen[pos] = 0;
}

/** Da-mi raspunsul la intrebarea curenta. **/
int giveAnswer() {
  int pos;

    //fprintf(stderr, "%d -> %d\n", heap.top(), seen[heap.top()]);
  while (seen[heap.top()] == 0) {
    //fprintf(stderr, "%d -> %d\n", heap.top(), seen[heap.top()]);
    heap.pop();
  }
  pos = heap.top();
  seen[pos] = 0;
  heap.pop();
  return val[pos];
}

int main(void) {
  int i, l, r;
  FILE *f = fopen("rmq.in", "r");

  /* Citirea datelor. */
  fscanf(f, "%d %d", &N, &M);
  int block = sqrt(N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &val[i]);
  }
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d", &query[i].l, &query[i].r);
    query[i].loc = query[i].l / block;
    query[i].init = i;
  }
  fclose(f);

  /* Sorteaza intrebarile. */
  sort(1, M);

  int left = 1, right = 0;

  /* Raspunde offline la intrebari. */
  for (i = 1; i <= M; i++) {
    l = query[i].l;
    r = query[i].r;

    //fprintf(stderr, "%d %d\n", l, r);

    while (right < r) {
      insert(right + 1);
      right++;
    }
    while (right > r) {
      erase(right);
      right--;
    }
    while (left > l) {
      insert(left - 1);
      left--;
    }
    while (left < l) {
      erase(left);
      left++;
    }
    answer[query[i].init] = giveAnswer();
  }

  /* Afisarea solutiei. */
  freopen("rmq.out", "w", stdout);
  for (i = 1; i <= M; i++) {
    fprintf(stdout, "%d\n", answer[i]);
  }
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}