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
def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [0]*(n+1)

        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i

        def sum(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s

    N,Q = map(int,input().split())
    C = list(map(int,input().split()))
    LR = []
    for i in range(Q):
        l,r = map(int,input().split())
        LR.append((l,r,i))
    bit = BIT(N)
    #color[i] => 色iが最後に登場したインデックス(1-indexed)
    color = [0]*(N+1)

    ANS = [0]*Q
    LR.sort(key=lambda x: x[1])
    cur = 1
    for l,r,j in LR:
        for i in range(cur,r+1):
            c = C[i-1]
            if color[c] != 0:
                bit.add(color[c],-1)
            color[c] = i
            bit.add(i,1)
        cur = r+1
        ANS[j] = bit.sum(r)-bit.sum(l-1)
    for a in ANS:
        print(a)
main()