The Little Elephant loves playing with arrays. He has array a, consisting of n positive integers, indexed from 1 to n. Let's denote the number with index i as ai. 

Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers alj, alj + 1, ..., arj.

Help the Little Elephant to count the answers to all queries.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, ..., an (1 ≤ ai ≤ 109). Next m lines contain descriptions of queries, one per line. The j-th of these lines contains the description of the j-th query as two space-separated integers lj and rj (1 ≤ lj ≤ rj ≤ n).

Output

In m lines print m integers — the answers to the queries. The j-th line should contain the answer to the j-th query.

Examples

Input

7 2
3 1 2 2 3 3 7
1 7
3 4


Output

3
1
#include <bits/stdc++.h>
using namespace std;
struct Point {
  int val;
  int index;
  Point() {}
  void display() {}
};
struct TimeFormat {
  int hour;
  int minute;
  TimeFormat() {}
  void display() {
    cout << hour << ":";
    if (minute < 10) {
      cout << "0" << minute;
    } else
      cout << minute;
  }
};
struct Appointment {
  TimeFormat start;
  TimeFormat end;
  string name;
  Appointment() {}
};
TimeFormat dist(TimeFormat a, TimeFormat b) {
  int minutea = a.hour * 60 + a.minute;
  int minuteb = b.hour * 60 + b.minute;
  int d = minuteb - minutea;
  TimeFormat ret;
  ret.hour = d / 60;
  ret.minute = d % 60;
  return ret;
}
bool cmpTimeFormat(TimeFormat a, TimeFormat b) {
  if (a.hour != b.hour) {
    return a.hour < b.hour;
  }
  return a.minute < b.minute;
}
bool cmpAppointment(Appointment a, Appointment b) {
  return cmpTimeFormat(a.start, b.start);
}
bool cmpPoint(Point a, Point b) {
  if (a.val != b.val) {
    return a.val < b.val;
  }
  return a.index < b.index;
}
int myabs(int x) { return x < 0 ? -x : x; }
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
int toInt(char xx) { return xx - '0'; }
char toChar(int xx) { return xx + '0'; }
bool isNum(char xx) { return ('0' <= xx && xx <= '9'); }
bool isCharacter(char xx) {
  return (('a' <= xx && xx <= 'z') || ('A' <= xx && xx <= 'Z'));
}
bool isUpper(char xx) { return ('A' <= xx && xx <= 'Z'); }
bool isLower(char xx) { return ('a' <= xx && xx <= 'z'); }
bool isPalin(string x) {
  int len = x.length();
  for (int i = 0; i <= len / 2; ++i) {
    if (x[i] != x[len - 1 - i]) return false;
  }
  return true;
}
bool cmp(char x, char y) {
  char xx = tolower(x);
  char yy = tolower(y);
  if (xx == yy) {
    return x < y;
  }
  return xx < yy;
}
long long val(long long x) {
  if (x < 0) return -x;
  return x;
}
const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
  if (rsz <= 0) {
    ptr = 0;
    rsz = fread(bf, 1, bfsz, stdin);
    if (rsz <= 0) return EOF;
  }
  --rsz;
  return bf[ptr++];
}
void ga(char &c) {
  c = EOF;
  while (!isalpha(c)) c = gc();
}
int gs(char s[]) {
  int l = 0;
  char c = gc();
  while (isspace(c)) c = gc();
  while (c != EOF && !isspace(c)) {
    s[l++] = c;
    c = gc();
  }
  s[l] = '\0';
  return l;
}
template <class T>
bool gi(T &v) {
  v = 0;
  char c = gc();
  while (c != EOF && c != '-' && !isdigit(c)) c = gc();
  if (c == EOF) return false;
  bool neg = c == '-';
  if (neg) c = gc();
  while (isdigit(c)) {
    v = v * 10 + c - '0';
    c = gc();
  }
  if (neg) v = -v;
  return true;
}
template <class T>
inline void checkmin(T &a, T b) {
  if (b < a) a = b;
}
const int maxn = 1e5 + 2;
int n, m;
int a[maxn];
int cnt[maxn], ans[maxn];
int l[maxn], r[maxn];
int cntX[maxn];
void readEachTest() {}
void initEachTest() {}
void solveEachTest() {}
void read() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    if (a[i] <= n) {
      cnt[a[i]]++;
    }
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &l[i], &r[i]);
  }
}
void init() {}
void solve() {
  for (int val = 1; val <= n; ++val) {
    if (cnt[val] >= val) {
      memset(cntX, 0, sizeof(cntX));
      for (int index = 1; index <= n; ++index) {
        cntX[index] = cntX[index - 1] + (a[index] == val ? 1 : 0);
      }
      for (int i = 1; i <= m; ++i) {
        if (cntX[r[i]] - cntX[l[i] - 1] == val) {
          ans[i]++;
        }
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    printf("%d\n", ans[i]);
  }
}
int main() {
  read();
  init();
  solve();
  return 0;
}
