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 position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
xx=1<<20
n,q=map(int,input().split())
a=list(map(int,input().split()))
a=position_zip(a,0)
k=max(a)+1
ans=[0]*q
queries=[]
for i in range(q):
  l,r=list(map(int,input().split()))
  l-=1
  r-=1
  queries.append(r<<40|l<<20|i)
queries.sort()
for i in range(q):
  ind=queries[i]%xx
  queries[i]>>=20
  l=queries[i]%xx
  queries[i]>>=20
  r=queries[i]
  queries[i]=(r,l,ind)
queries.append((10*20,0,0))
lastAppeared=[-1]*k
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]]!=-1:
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  while queries[j][0]==i:
    r,l,ind=queries[j]
    j+=1
    ans[ind]=bitt.sum(l,r-1)
print(*ans)
