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
import sys
def main():
  n,q,*c=map(int,sys.stdin.buffer.read().split())
  a=[0]*q
  j,*b=t=[0]*9**6
  for i in sorted(range(q),key=lambda x:c[x+x-~n]):
    l,r=c[i+i+n],c[i+i-~n]
    while j<r:
      k=c[j]
      j+=1
      x,y,b[k]=b[k]+1,j+1,j
      while x<=n:
        t[x]+=1
        x=x+(x&-x)
      while y<=n:
        t[y]-=1
        y=y+(y&-y)
    s=0
    while l:
      s=s+t[l]
      l=l-(l&-l)
    a[i]=s
  print(' '.join(map(str,a)))
main()