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
NN = 19
XX = [0] * (2**(NN+1)-1)

def addvalue(j, x):
    i = 2**NN + j - 1
    while i >= 0:
        XX[i] += x
        i = (i-1) // 2

def rangesum(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    s = 0
    while l < r:
        if l%2:
            s += XX[l-1]
            l += 1
        if r%2:
            r -= 1
            s += XX[r-1]
        l >>= 1
        r >>= 1
    return s

N, Q = map(int, input().split())
C = [int(a) - 1 for a in input().split()]
X = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    X[r-1].append((l - 1, i))
last = [-1] * N
ANS = [-1] * Q
addvalue(1, N)
for r in range(N):
    c = C[r]
    addvalue(last[c] + 2, -1)
    addvalue(r + 2, 1)
    last[c] = r
    for l, i in X[r]:
        ANS[i] = rangesum(l + 2, 1 << NN)
    
print(*ANS, sep = "\n")