220_B. Little Elephant and Array
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
```python
# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/8/20

for each query l, r; how many x that count of x in range [l, r] equals x

for each query ends with x, query (l, x) with Fenwick tree

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List


def solve(N, M, A, Q):
    
    bit = [0 for _ in range(N)]
    
    def add(index, val):
        while index < N:
            bit[index] += val
            index |= index + 1
        
    def query(index):
        index = min(index, N-1)
        s = 0
        while index >= 0:
            s += bit[index]
            index = (index & (index + 1)) - 1
        
        return s
    
    q = collections.defaultdict(list)
    for i, (l, r) in enumerate(Q):
        q[r].append((l, i))
    
    ans = [0 for _ in range(M)]
    vi = collections.defaultdict(list)
    for i, v in enumerate(A):
        u = vi[v]
        u.append(i)
        lv = len(vi[v])
        if lv >= v:
            add(u[-v], 1)
            if lv >= v + 1:
                add(u[-v-1], -2)
            if lv >= v + 2:
                add(u[-v-2], 1)
        
        for l, qi in q[i]:
            ans[qi] = query(i) - query(l-1)
    
    print('\n'.join(map(str, ans)))


def test():
    N, M = 100000, 100000
    import random
    A = [random.randint(0, 1000) for _ in range(N)]
    Q = []
    for i in range(M):
        l = random.randint(0, N-1)
        r = random.randint(l, N-1)
        Q.append((l, r))
    solve(N, M, A, Q)

# test()


N, M = map(int, input().split())
A = [int(x) for x in input().split()]
Q = []
for i in range(M):
    l, r = map(int, input().split())
    Q.append((l-1, r-1))
    
solve(N, M, A, Q)
```