#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;


__attribute__((always_inline)) void read(int &num) {
  static char inBuffer[0x30D40];

  static unsigned int p = 0x30D3F;
  num = 0x0;

  while(inBuffer[p] < 0x30 | inBuffer[p] > 0x39) {
    ++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
  }

  while(inBuffer[p] > 0x2F & inBuffer[p] < 0x3A) {
    num = num * 0xA + inBuffer[p] - 0x30;

    ++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
  }
}

char outBuffer[0x61A80];
unsigned int p;

__attribute__((always_inline)) void write(unsigned int x) {
  unsigned int digits = x > 0x3B9AC9FF ? 0xA :
                        x > 0x5F5E0FF  ? 0x9 :
                        x > 0x98967F   ? 0x8 :
                        x > 0xF423F    ? 0x7 :
                        x > 0x1869F    ? 0x6 :
                        x > 0x270F     ? 0x5 :
                        x > 0x3E7      ? 0x4 :
                        x > 0x63       ? 0x3 :
                        x > 0x9        ? 0x2 : 0x1;

  for(unsigned int i = ~ -digits; ~i; --i) {
    outBuffer[p + i] = x % 0xA + 0x30;

    x = x / 0xA;
  }

  p = p + digits;
  outBuffer[p++] = 0x20;
}


const int N = 300000 + 7;
const int INF = (int) 1e9;
int n, q, a[N];
vector <pair <int, int>> need[N];
int ans[2 * N];

int tree[4 * N];

void upd(int v, int tl, int tr, int p, int t) {
  if (p < tl || tr < p)
    return;
  if (tl == tr)
    tree[v] = t;
  else {
    int tm = (tl + tr) / 2;
    upd(2 * v, tl, tm, p, t);
    upd(2 * v + 1, tm + 1, tr, p, t);
    tree[v] = min(tree[2 * v], tree[2 * v + 1]);
  }
}

int get(int v, int tl, int tr, int p) {
  if (p < tl)
    return INF;
  if (tr <= p)
    return tree[v];
  else {
    int tm = (tl + tr) / 2;
    return min(get(2 * v, tl, tm, p), get(2 * v + 1, tm + 1, tr, p));
  }
}

int ns, L;

int bn(int v, int tl, int tr) {
  if (tl == tr)
    ns = tl;
  else {
    int tm = (tl + tr) / 2;
    if (tree[2 * v] < L)
      bn(2 * v, tl, tm);
    else
      bn(2 * v + 1, tm + 1, tr);
  }
}

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

  for (int i = 0; i < 4 * N; i++)
    tree[i] = -1;

  read(n);
  read(q);
  for (int i = 0; i < n; i++)
    read(a[i]);
  for (int i = 0; i < q; i++) {
    int l, r;
    read(l);
    read(r);
    need[r].push_back({l, i});
  }
  for (int r = 0; r < n; r++) {
    upd(1, 1, N - 1, a[r], r);
    for (auto &it : need[r]) {
      L = it.first;
      int i = it.second;
      bn(1, 1, N - 1);
      ans[i] = ns;
    }
  }
  for (int i = 0; i < q; i++) {
    write(ans[i]);
    if (i < q - 1)
      outBuffer[p++] = '\n';
  }
  puts(outBuffer);
  return 0;
}