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;
float root;
struct Interval {
  vector<int> interval;
  int position;
  int answer;
  Interval() { interval.resize(2); }
};
bool compareIntervals(Interval &i, Interval &j) {
  int group1 = ceil(i.interval[0] / root);
  int group2 = ceil(j.interval[0] / root);
  if (group1 != group2) {
    return group1 < group2;
  }
  int size1 = i.interval[1] - i.interval[0];
  int size2 = j.interval[1] - j.interval[0];
  if (size1 == size2) {
    return i.interval[1] < j.interval[1];
  }
  return size1 < size2;
};
bool comparePositions(Interval &i, Interval &j) {
  return i.position < j.position;
};
int main() {
  int n;
  scanf("%d", &n);
  int numOfQueries;
  scanf("%d", &numOfQueries);
  root = ceil(sqrt(n));
  vector<Interval> intervals(numOfQueries);
  int maxNum = 100001;
  vector<int> freq(maxNum);
  vector<int> nums(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &nums[i]);
  }
  for (int i = 0; i < numOfQueries; i++) {
    intervals[i].position = i;
    scanf("%d", &intervals[i].interval[0]);
    scanf("%d", &intervals[i].interval[1]);
  }
  sort(intervals.begin(), intervals.end(), compareIntervals);
  int oldLeft = intervals[0].interval[0] - 1;
  int oldRight = intervals[0].interval[1] - 1;
  int sum = 0;
  for (int i = oldLeft; i <= oldRight; i++) {
    int num = nums[i];
    if (num < maxNum) {
      freq[num]++;
      if (freq[num] - 1 == num) {
        sum--;
      } else if (freq[num] == num) {
        sum++;
      }
    }
  }
  for (int i = 0; i < numOfQueries; i++) {
    int newLeft = intervals[i].interval[0] - 1;
    int newRight = intervals[i].interval[1] - 1;
    if (oldLeft < newLeft) {
      for (int j = oldLeft; j < newLeft; j++) {
        int num = nums[j];
        if (num < maxNum) {
          freq[num]--;
          if (freq[num] + 1 == num) {
            sum--;
          } else if (freq[num] == num) {
            sum++;
          }
        }
      }
    } else if (oldLeft > newLeft) {
      for (int j = oldLeft - 1; j >= newLeft; j--) {
        int num = nums[j];
        if (num < maxNum) {
          freq[num]++;
          if (freq[num] - 1 == num) {
            sum--;
          } else if (freq[num] == num) {
            sum++;
          }
        }
      }
    }
    if (oldRight < newRight) {
      for (int j = oldRight + 1; j <= newRight; j++) {
        int num = nums[j];
        if (num < maxNum) {
          freq[num]++;
          if (freq[num] - 1 == num) {
            sum--;
          } else if (freq[num] == num) {
            sum++;
          }
        }
      }
    } else if (oldRight > newRight) {
      for (int j = oldRight; j > newRight; j--) {
        int num = nums[j];
        if (num < maxNum) {
          freq[num]--;
          if (freq[num] + 1 == num) {
            sum--;
          } else if (freq[num] == num) {
            sum++;
          }
        }
      }
    }
    intervals[i].answer = sum;
    oldLeft = newLeft;
    oldRight = newRight;
  }
  sort(intervals.begin(), intervals.end(), comparePositions);
  for (int i = 0; i < numOfQueries; i++) {
    printf("%d\n", intervals[i].answer);
  }
}
