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

#define MAX_M 1000000
#define MAX_N 100000

const int POW = (1 << 12) - 1;

int save;
struct list {
  unsigned int _next;
  char _v;

  list() {

  }

  list(int _next, int _v) {
    this -> _next = ((unsigned)_next << 12) | (_v & POW);
    this -> _v = _v >> 12;
  }

  int next() {
    return this -> _next >> 12;
  }

  int v() {
    save = this -> _v;
    return (this -> _next & POW) + (save << 12);
  }
};

int N, M;
int lg[MAX_N + 2];
int val[MAX_N + 1];
list l[MAX_M + 1];
int adj[MAX_N + 1];
int ss, stack[MAX_N + 1];
int dig[20];

#define MAX_OUT 7000000
#define MAX_BUFF 65536
int ptr = MAX_BUFF;
char buff[MAX_BUFF];
char out[MAX_OUT + 1];
int result;
char c;

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

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

void afis() {
  for (int i =0 ; i<ss; i++){
    fprintf(stderr, "%d ", stack[i]);
  }
  fprintf(stderr, "\n");
}

void push(int pos) {
  while (ss && val[pos] <= val[stack[ss - 1]]) {
    ss--;
  }
  stack[ss++] = pos;
}

int binSearch(int v) {
  if (v <= stack[0]) {
    return stack[0];
  }
  int x = 0, pas = 1 << lg[ss];
  while (pas) {
    if (x + pas < ss && stack[x + pas] < v) {
      x += pas;
    }
    pas >>= 1;
  }
  return stack[x + 1];
}

void put(int x) {
  if (x == 0) {
    dig[ss++] = 0;
  }
  while (x) {
    save = x / 10;
    dig[ss++] = x - (save << 3) - (save << 1);
    x = save;
  }

  while (ss) {
    out[ptr++] = dig[ss - 1] + '0';
    ss--;
  }
  out[ptr++] = '\n';
}

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

  N = freef(f);
  M = freef(f);
  lg[1] = 0;
  for (i = 1; i <= N; i++) {
    val[i] = freef(f);
    lg[i + 1] = lg[(i + 1) >> 1] + 1;
  }
  for (i = 1; i <= M; i++) {
    a = freef(f);
    b = freef(f);
    l[i] = list(adj[b], a);
    adj[b] = i;
  }
  fclose(f);

  int pos;
  for (i = 1; i <= N; i++) {
    push(i);
    for (pos = adj[i]; pos; pos = l[pos].next()) {
      l[pos] = list(l[pos].next(), val[binSearch(l[pos].v())]);
    }
  }

  ptr = ss = 0;
  for (i = 1; i <= M; i++) {
    put(l[i].v());
  }

  freopen("rmq.out", "w", stdout);
  fwrite(out, 1, ptr, stdout);
  fclose(stdout);
  return 0;
}