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

#include <queue>
#include <vector>

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

#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];
char seen[Nadejde + 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)));
}

void insertionSort(int lo, int hi) {
  for (int i = lo; i < hi; ++ i) {
    ull int x = query[i];
    int j = i;
    while (j > lo && cmp(x, query[j - 1])) {
      query[j] = query[j - 1];
      -- j;
    }
    query[j] = x;
  }
}

void radixPass(int lo, int hi, int bits) {
#define BITS 8
  int ptr[1 << BITS], end[1 << BITS] = {};
  for (int i = lo; i < hi; ++ i) {
    ++ end[((query[i] & MASK(26)) >> bits) & MASK(BITS)];
  }
  ptr[0] = lo;
  end[0] += lo;
  for (int i = 1; i < (1 << BITS); ++ i) {
    ptr[i] = end[i - 1];
    end[i] += end[i - 1];
  }
  for (int i = 0; i < (1 << BITS); ++ i) {
    while (ptr[i] != end[i]) {
      ull int elem = query[ptr[i]];
      int bucket = ((elem & MASK(26)) >> bits) & MASK(BITS);
      while (bucket != i) {
        ull int tmp = query[ptr[bucket]];
        query[ptr[bucket]++] = elem;
        elem = tmp;
        bucket = ((elem & MASK(26)) >> bits) & MASK(BITS);
      }
      query[ptr[i]++] = elem;
    }
  }
  if (bits) {
    for (int i = 0; i < (1 << BITS); ++ i) {
      int size = end[i] - (i ? end[i - 1] : lo);
      if (size > 64) {
        radixPass(end[i] - size, end[i], bits - BITS);
      } else if (size > 1) {
        insertionSort(end[i] - size, end[i]);
      }
    }
  }
}

typedef struct {
  int size;
  int v[Nadejde * 10];
} 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) {
  /*if (!seen[pos]) {
    heap.push(pos);
  } else {
    //fprintf(stderr, "......%d\n", h.size);
  }
  */
  if (!seen[pos]) {
    push(pos);
  }
  seen[pos] = 1;
}

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

/** 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];
}

void test(int ads) {
  fprintf(stderr, "%d\n", ads);
}

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);
    //index[i] = i;
  }
  fclose(f);

  /* Sorteaza intrebarile. */
  radixPass(1, M + 1, 24);

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

  int left = 1, right = 0;

  //fprintf(stderr, "iese");

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

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

    while (right < r) {
      //fprintf(stderr, "Intrdu %d\n", right + 1);
      ///test(0);
      insert(right + 1);
      right++;
    }
    while (left > l) {
      //fprintf(stderr, "Introdu %d\n", left - 1);
      ///test(1);
      insert(left - 1);
      left--;
    }
    while (right > r) {
      //fprintf(stderr, "Shhcoate %d\n", right);
      ///test(2);
      erase(right);
      right--;
    }
    while (left < l) {
      //fprintf(stderr, "Scoate %d\n", left);
      ///test(3);
      erase(left);
      left++;
    }
    answer[init(query[i])] = giveAnswer();
    //fprintf(stderr, "%d\n", answer[init(query[index[i]])]);
     //exit(0);
  }

  /* 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;
}