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
I=lambda:map(int,input().split())
N=0xfffff
n,q=I()
c=list(I())
Q=[]
R=range
for i in R(q):l,r=I();Q.append(l<<40|r<<20|i)
Q.sort()
A=[[]for i in R(N)]
for i in R(n):A[c[i]].append(i)
B=[0]*N
def P(i,x):
	i+=1
	while i<=n:B[i]+=x;i+=i&-i
for i in A:
	if i:P(i[0],1);i.reverse()
t=0
o=[0]*q
for x in Q:
	l=(x>>40)-1
	r=x>>20&N
	i=x&N
	while t<l:
		b=A[c[t]]
		P(b[-1],-1)
		b.pop()
		if b:P(b[-1],1)
		t+=1
	while r:o[i]+=B[r];r-=r&-r
	while l:o[i]-=B[l];l-=l&-l
for i in o:print(i)