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

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

#define Smerenie 1000000
#define Nadejde 100000

#define ull unsigned long long

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

inline unsigned int MASK(int x) {
  return (1 << x) - 1;
}

struct cell {
  ull int set;

  int l() const {
    return set & MASK(17);
  }

  int r() const {
    return (set >> 17) & MASK(17);
  }

  int init() const {
    return (set >> 34) & MASK(20);
  }

  int loc() const {
    return (set >> 54) & MASK(9);
  }

  void update(int l, int r, int loc, int init) {
    this -> set = (ull)l;
    this -> set |= ((ull)r << 17);
    this -> set |= ((ull)init << 34);
    this -> set |= ((ull)loc << 54);
  }
};

int N, M;
int sum;
int val[Nadejde + 1];
int 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. **/
inline 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. **/
inline void insert(int pos) {
  heap.push(pos);
  seen[pos]++;
}

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

/** Da-mi raspunsul la intrebarea curenta. **/
inline 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]--;
  //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", &l, &r);
    query[i].update(l, r, l / block, i);
  }
  fclose(f);

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

  //fprintf(stderr, "asdas\n");

  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) {
      //fprintf(stderr, "Intrdu %d\n", right + 1);
      insert(right + 1);
      right++;
    }
    while (left > l) {
      //fprintf(stderr, "Introdu %d\n", left - 1);
      insert(left - 1);
      left--;
    }
    while (right > r) {
      //fprintf(stderr, "Shhcoate %d\n", right);
      erase(right);
      right--;
    }
    while (left < l) {
      //fprintf(stderr, "Scoate %d\n", left);
      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;
}