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
'''input
7 2
3 1 2 2 3 3 7
1 7
3 4
'''

''' Given an array, tell count of values in range [l,r] repeated at least 3 times
'''
from collections import defaultdict

ans = 0
def main():

    def add(pos):
        global ans
        if count[arr[pos]] == arr[pos]: ans -= 1
        count[arr[pos]] += 1
        if count[arr[pos]] == arr[pos]: ans += 1


    def remove(pos):
        global ans
        if count[arr[pos]] == arr[pos]: ans -= 1
        count[arr[pos]] -= 1
        if count[arr[pos]] == arr[pos]: ans += 1

    def cmp(a, b):
        if a[-1] == b[-1]:
            if a[-1]%2==0:
                return 1 if a[1] > b[1] else -1             # Right limit
            else:
                return -1 if a[1] > b[1] else 1             # Right limit
        return 1 if a[-1] > b[-1] else -1               # Band wise



    count = defaultdict(int)
    currL, currR= 0, 0
    n, q = map(int, raw_input().split())
    band = int(n**0.5 + 0.5)
    arr = map(int, raw_input().split())
    queries = []
    for i in range(q):
        a, b = map(int, raw_input().split())
        # 0 inexing
        a-=1; b-=1
        queries.append((a,b, i, a/band))


    queries.sort(cmp)

    anss = []
    # ans at any time contains for [currL, currR)
    for query in queries:
        L,R, pos, blok = query
        while currL < L: remove(currL); currL+=1
        while currL > L: add(currL-1);  currL-=1
        while currR <= R: add(currR); currR+=1
        while currR > R+1: remove(currR-1); currR-=1
        anss.append((pos, ans))

    anss.sort()
    for val in anss:
        print val[1]

main()
