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

#define Smerenie 1000000
#define Nadejde 100000
#define Dragoste 4096

#define ull unsigned long long

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

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

int ptr = Dragoste;
char buff[Dragoste];

char getChar(FILE *f) {
  if (ptr == Dragoste) {
    fread(buff, 1, Dragoste, f);
    ptr = 0;
  }
  return buff[ptr++];
}

int freef(FILE *f) {
  int result = 0;
  char c;

  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    result = (result << 3) + (result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
  return result;
}

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

int _r(ull int set) {
  return set & MASK(17);
}

int _l(ull int set) {
  return (set >> 26) & MASK(17);
}

int init(ull int set) {
  return (set >> 43) & MASK(20);
}
/*
int loc(ull int set) {
  return (set >> 17) & MASK(9);
}
*/
ull int update(int l, int r, int loc, int init) {
  ull int set;

  set = (ull)r;
  set |= ((ull)loc << 17);
  set |= ((ull)l << 26);
  set |= ((ull)init << 43);
  return set;
}

/** Cmp-ul pentru sortarea din algoritmul lui Mo. **/
inline int cmp(ull int X, ull int &Y) {
  return ((X & MASK(26)) < (Y & MASK(26)));
}

/** Sortarea lui Mo. **/
void sort(int begin, int end) {
  int b = begin, e = end;
  ull int 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);
  }
}

typedef struct {
  int size;
  int v[Nadejde + 1];
} heap;

heap h;

/** Interschimba valorile "X" si "Y". **/
void swap(int *X, int *Y) {
  int tmp = *X;
  *X = *Y;
  *Y = tmp;
}

/** Prioritatea heapului: parintele sa aibe valoarea mai ca a fiului. **/
int priority(int dad, int son) {
  return (val[h.v[dad]] < val[h.v[son]]);
}

/** Adauga in heap valorea "x":
 *  Pune valoarea in ultima pozitie din heap si o promoveaza catre varf,
 * verificand pe fiecare nivel daca el este mai mic decat parintele sau.
**/
void push(int x) {
  h.v[++h.size] = x;

  int dad, pos = h.size;
  for (dad = pos >> 1; (pos > 1) && (!priority(dad, pos)); dad = pos >> 1) {
    swap(&h.v[pos], &h.v[dad]);
    pos = dad;
  }
}

/** Arunca varful heapului si reseteaza heap-ul:
 *  In locul varfului pune valoarea de pe ultima pozitie din heap. Dupa asta propaga varful
 * in heap pana este respectata structura de min-heap.
**/
void pop() {
  h.v[1] = h.v[h.size--];

  int left, right, pos = 1, son = 1;
  do {
    /* Interschimba cele doua noduri. */
    swap(&h.v[pos], &h.v[son]);
    pos = son;

    left = pos << 1;
    right = left + 1;

    /* Verifica daca "pos" nu este o frunza. */
    if (left <= h.size) {
      son = left;

      /* Alege fiul cu valoarea cea mai mica. */
      if ((right <= h.size) && (priority(right, left))) {
        son = right;
      }
      if (priority(pos, son)) {
        son = pos;
      }
    }
  } while (pos != son);
}

/** Da-mi varful heap-ului. **/
int top() {
  return h.v[1];
}

/** Functii stas: **/

/** Inserare. **/
inline void insert(int pos) {
  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[top()] == 0) {
    //fprintf(stderr, "%d -> %d\n", heap.top(), seen[heap.top()]);
    pop();
  }
  pos = top();
  //seen[pos]--;
  //heap.pop();
  return val[pos];
}

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

  /* Citirea datelor. */
  N = freef(f);
  M = freef(f);
  int block = sqrt(N);
  for (i = 1; i <= N; i++) {
    val[i] = freef(f);
  }
  for (i = 1; i <= M; i++) {
    l = freef(f);
    r = freef(f);
    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 = _l(query[i]);
    r = _r(query[i]);

    //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[init(query[i])] = 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;
}