#include <bits/stdc++.h>
using namespace std;
int ans[300010];
int test[300010];
struct LR {
  int l;
  int r;
  int id;
};
LR lrs[300010];
bool cmp(LR a, LR b) { return a.l > b.l; }
struct seg {
  int l;
  int r;
  int val;
  int tag;
};
seg T[300010 * 4];
void build(int I, int l, int r) {
  T[I].l = l;
  T[I].r = r;
  T[I].tag = 0;
  if (l == r) {
    T[I].val = l - test[l];
    if (T[I].val < 0) {
      T[I].val = 0x6fffffff;
    }
  } else {
    build(2 * I, l, (l + r) / 2);
    build(2 * I + 1, (l + r) / 2 + 1, r);
    T[I].val = min(T[2 * I].val, T[2 * I + 1].val);
  }
}
void push(int I) {
  T[2 * I].tag += T[I].tag;
  T[2 * I].val -= T[I].tag;
  T[2 * I + 1].tag += T[I].tag;
  T[2 * I + 1].val -= T[I].tag;
  T[I].tag = 0;
}
int findrmin(int I, int l, int r) {
  int L = T[I].l, R = T[I].r, ret;
  if (T[I].val == 0) {
    if (L == l && R == r && L == R) {
      return l;
    }
    push(I);
    if (L == l && R == r) {
      if (T[2 * I + 1].val == 0) {
        return findrmin(2 * I + 1, (L + R) / 2 + 1, R);
      }
      return findrmin(2 * I, L, (L + R) / 2);
    }
    if (r <= (L + R) / 2) {
      return findrmin(2 * I, l, r);
    }
    if (l >= (L + R) / 2 + 1) {
      return findrmin(2 * I + 1, l, r);
    }
    ret = findrmin(2 * I + 1, (L + R) / 2 + 1, r);
    if (ret != -1) {
      return ret;
    }
    return findrmin(2 * I, l, (L + R) / 2);
  }
  return -1;
}
void change(int I, int it) {
  int L = T[I].l, R = T[I].r;
  if (L == R && R == it) {
    T[I].val = 0x6fffffff;
    return;
  }
  if (it <= (L + R) / 2) {
    change(2 * I, it);
    T[I].val = min(T[2 * I].val, T[2 * I + 1].val);
    return;
  }
  if (it >= (L + R) / 2 + 1) {
    change(2 * I + 1, it);
    T[I].val = min(T[2 * I].val, T[2 * I + 1].val);
    return;
  }
}
void add(int I, int l, int r) {
  int L = T[I].l, R = T[I].r;
  if (L == l && R == r) {
    T[I].val--;
    T[I].tag++;
    return;
  }
  push(I);
  if (r <= (L + R) / 2) {
    add(2 * I, l, r);
    T[I].val = min(T[2 * I].val, T[2 * I + 1].val);
    return;
  }
  if (l >= (L + R) / 2 + 1) {
    add(2 * I + 1, l, r);
    T[I].val = min(T[2 * I].val, T[2 * I + 1].val);
    return;
  }
  add(2 * I, l, (L + R) / 2);
  add(2 * I + 1, (L + R) / 2 + 1, r);
  T[I].val = min(T[2 * I].val, T[2 * I + 1].val);
  return;
}
seg AT[300010 * 4];
void buildA(int I, int l, int r) {
  AT[I].l = l;
  AT[I].r = r;
  AT[I].tag = 0;
  AT[I].val = 0;
  if (l != r) {
    buildA(2 * I, l, (l + r) / 2);
    buildA(2 * I + 1, (l + r) / 2 + 1, r);
  }
}
void addA(int I, int it) {
  int L = AT[I].l, R = AT[I].r;
  if (L == R) {
    AT[I].val++;
    return;
  }
  if (it <= (L + R) / 2) {
    addA(2 * I, it);
    AT[I].val = AT[2 * I].val + AT[2 * I + 1].val;
    return;
  }
  if (it >= (L + R) / 2 + 1) {
    addA(2 * I + 1, it);
    AT[I].val = AT[2 * I].val + AT[2 * I + 1].val;
    return;
  }
}
int search(int I, int l, int r) {
  int L = AT[I].l, R = AT[I].r;
  if (l == L && R == r) {
    return AT[I].val;
  }
  if (r <= (L + R) / 2) {
    return search(2 * I, l, r);
  }
  if (l >= (L + R) / 2 + 1) {
    return search(2 * I + 1, l, r);
  }
  return search(2 * I, l, (L + R) / 2) + search(2 * I + 1, (L + R) / 2 + 1, r);
}
int main() {
  int n, q, it;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> test[i];
  }
  for (int i = 0; i < q; i++) {
    cin >> lrs[i].l >> lrs[i].r;
    lrs[i].id = i;
  }
  sort(lrs, lrs + q, cmp);
  build(1, 1, n);
  buildA(1, 1, n);
  for (int i = 0; i < q; i++) {
    it = findrmin(1, lrs[i].l + 1, n);
    while (it != -1) {
      change(1, it);
      addA(1, it);
      if (it < n) {
        add(1, it + 1, n);
      }
      it = findrmin(1, lrs[i].l + 1, n);
    }
    ans[lrs[i].id] = search(1, lrs[i].l + 1, n - lrs[i].r);
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}
