#include <stdio.h>
#include <stdlib.h>
#define N 200000
#define log(x) 31 - __builtin_clz(x)

static const int b = 30;
int n, euler[(N<<1)+1], niv[N<<1], first[N<<1], v[N+1],
    mask[N], seg[log(N/b)+2][N], parent[N+1], s[N+1], size;

int cmp (int a, int b) {
  return niv[euler[a]] < niv[euler[b]] ? a : b;
}

int trans (int x, int base = b) {
  return x - (log(mask[x] & ((1 << base) - 1)));
}

int query (int x, int y) {
  if (y - x + 1 <= b)
    return euler[trans(y, y-x+1)];
  int ans = cmp(trans(x + b - 1), trans(y));

  x /= b; ++x;
  y /= b; --y;
  if (x <= y) {
    int lg = log(y-x+1);
    ans = cmp(ans, cmp(seg[lg][x], seg[lg][y - (1<<lg) + 1]));
  }
  return euler[ans];
}

struct nod {
  int inf;
  struct nod* urm;
} *G[N+1];

void add (int x, int i) {
  struct nod *e = (struct nod*) malloc(sizeof (struct nod));
  e->inf = i;
  e->urm = G[x];

  G[x] = e;
}

void dfs (int x, int from = 0) {
  euler[size++] = x;
  niv[x] = niv[from] + 1;

  for (; G[x]; G[x]=G[x]->urm)
    if (G[x]->inf != from) {
      first[G[x]->inf] = size;
      dfs(G[x]->inf, x);
    }
  euler[size++] = from;
}

int main (void) {
  freopen("rmq.in", "r", stdin);
  freopen("rmq.out", "w", stdout);

  int q, i, j;
  scanf("%d%d", &n, &q);

  int top = 0, last;
  for (i=1; i<=n; ++i)
    scanf("%d", v+i);

  for (i=1; i<=n; ++i) {
    last = 0;
    while (top && v[s[top]] >= v[i]) {
      last = s[top];
      --top;
    }

    if (top) {
      parent[i] = s[top];
      add(s[top], i);
    }
    if (last) {
      parent[last] = i;
      add(i, last);
    }
    s[++top] = i;
  }

  i=1;
  while (parent[i])
    i = parent[i];
  dfs(i);

  n = size;
  int at = 0;
  for (i=0; i<n; ++i) {
    at = (at << 1) & ((1<<b) - 1);
    while (at && cmp(i, i - __builtin_ctz(at)) == i)
      at ^= at & -at;
    at |= 1;
    mask[i] = at;
  }

  n /= b;
  for (i=0; i<n; ++i)
    seg[0][i] = trans(b*i + b - 1);

  for (i=1; (1<<i) < n; ++i)
    for (j=0; j + (1<<i) <= n; ++j)
      seg[i][j] = cmp(seg[i-1][j], seg[i-1][j + (1<<i-1)]);

  int x, y;
  for (; q; --q) {
    scanf("%d%d", &x, &y);
    x = first[x];
    y = first[y];

    if (x > y) {
      i = x;
      x = y;
      y = i;
    }

    printf("%d\n", v[query(x, y)]);
  }
  return 0;
}