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 add(i,x):
    global BIT
    i+=1
    while i<=n:
        BIT[i] += x
        i += i&(-i)
        
def bitsum(i):
    x = 0
    i+=1
    while i>0:
        x += BIT[i]
        i -= i&(-i)
    return x

def sums(l,r):
    return bitsum(r-1)-bitsum(l-1)

n,q = map(int,input().split())
c = list(map(int,input().split()))
pi = [-1]*(n+1)
ps = [[] for _ in range(n)]
qs = [[] for _ in range(n)]
for i in range(n):
    l = pi[c[i]]
    if l!=-1:
        ps[l].append(i)
    pi[c[i]] = i
for i in range(q):
    l,r = map(int,input().split())
    l,r = l-1,r-1
    qs[l].append((r,i))
BIT = [0]*(n+1)
ans = [None]*q
for x in range(n-1,-1,-1):
    for y in ps[x]:
        add(y,1)
    for r,i in qs[x]:
        ans[i] = r-x+1-bitsum(r)

for i in ans:
    print(i)