#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];
int seen[Nadejde + 1];
int answer[Smerenie + 1];
ull int query[Smerenie + 1];

int ptr = Dragoste;
char buff[Dragoste];

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

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

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]);
      }
    }
  }
}

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

/** Functii stas: **/

/** Inserare. **/
inline void insert(int pos) {
  /*if (!seen[pos]) {
    heap.push(pos);
  } else {
    //fprintf(stderr, "......%d\n", h.size);
  }
  */
  heap.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[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];
}

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