We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

* 1\leq N,Q \leq 5 \times 10^5
* 1\leq c_i \leq N
* 1\leq l_i \leq r_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q


Output

Print Q lines. The i-th line should contain the response to the i-th query.

Examples

Input

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


Output

2
3
1


Input

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8


Output

1
2
2
1
2
2
6
3
3
3
from sys import stdin

class BIT:
    def __init__(self, n):
        self.data = [0] * (n + 10)
        
    def upd(self, pos, val = 1):
        pos += 1
        while pos < len(self.data):
            self.data[pos] += val
            pos += pos & -pos
            
    def get(self, pos):
        ans = 0
        pos += 1
        while pos > 0:
            ans += self.data[pos]
            pos -= pos & -pos
        return ans
    
    def get_range(self, l, r):
        return self.get(r) - self.get(l - 1)

def main():
    n, q = map(int, stdin.readline().split())
    color = list(map(int, stdin.readline().split()))
    
    queries = []
    for i in range(q):
        l, r = map(int, stdin.readline().split())
        queries.append((l, r, i))
    queries.sort(key = lambda val: val[1])
    
    ans = [0] * q
    prev_pos = [0] * (n + 1)
    bit = BIT(n + 1)
    
    f = 0
    for cur_pos, color in enumerate(color, 1):
        bit.upd(prev_pos[color], -1)
        bit.upd(cur_pos, 1)
        prev_pos[color] = cur_pos
        
        while f < q and queries[f][1] == cur_pos:
            ans[queries[f][2]] = bit.get_range(queries[f][0], queries[f][1])
            f += 1
    print('\n'.join(map(str, ans)))
    
main()
