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

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

#define ull unsigned long long

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

inline 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;
  }
}

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

int heap[Nadejde];
int heapPos[Nadejde + 1];
int heapSize;

void swap(int &X, int &Y) {
  int tmp = X;
  X = Y;
  Y = tmp;
}

void downHeap(int u) {
    int best, changed;

    do {
        best = u;
        changed = 0;
        for (int i = 1; i <= 2; ++ i) {
            if (u + u + i < heapSize && val[heap[u + u + i]] < val[heap[best]]) {
                best = u + u + i;
            }
        }
        if (best != u) {
            changed = 1;
            heapPos[heap[best]] = u;
            heapPos[heap[u]] = best;
            swap(heap[u], heap[best]);
            u = best;
        }
    } while (changed);
}

void upHeap(int u) {
    int father = (u - 1) >> 1;
    while (u > 0 && val[heap[father]] > val[heap[u]]) {
        heapPos[heap[father]] = u;
        heapPos[heap[u]] = father;
        swap(heap[u], heap[father]);
        u = father;
        father = (u - 1) >> 1;
    }
}

/** Functii stas: **/

/** Inserare. **/
inline void insert(int pos) {
  //cin >> v[heapSize];
  heap[heapSize] = pos;
  heapPos[pos] = heapSize;
  upHeap(heapSize);
  ++heapSize;
}

/** Stergere. **/
inline void erase(int pos) {
  heap[heapPos[pos]] = heap[heapSize - 1];
  heapPos[heap[heapSize - 1]] = heapPos[pos];
  --heapSize;

  if (heapPos[pos] > 0 && val[heap[(heapPos[pos] - 1) >> 1]] > val[heap[heapPos[pos]]]) {
      upHeap(heapPos[pos]);
  } else {
      downHeap(heapPos[pos]);
  }
}

/** Da-mi raspunsul la intrebarea curenta. **/
inline int giveAnswer() {
  return val[heap[0]];
}

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. */
  radixPass(1, M + 1, 24);

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

    while (right < r) {
      insert(right + 1);
      right++;
    }
    while (left > l) {
      insert(left - 1);
      left--;
    }
    while (right > r) {
      erase(right);
      right--;
    }
    while (left < l) {
      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;
}