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
input = sys.stdin.readline

def update(index, value, bit):
  #print('update', index, value)
  while index < len(bit):
    #print('update', index)
    bit[index] += value
    index += index & -index
  #print('done')
    
    
def cumsum(index, bit):
  ans = 0
  while index > 0:
    #print('cumsum', index)
    ans += bit[index]
    index -= index & -index
  #print('done', ans)
  return ans
  

def main():
  N, q = [int(x) for x in input().split()]
  C = [int(x)-1 for x in input().split()]
  Q = []
  for i in range(q):
    l, r =  [int(x)-1 for x in input().split()]
    Q.append((i, l, r))
  Q.sort(key=lambda x: x[2])
  leftmost = [-1] * N
  bit = [0] * (N+1)
  prev = -1
  ans = [0] * q
  for i, l, r in Q:
    #print(i, r, l)
    to_update = {}
    for x in range(prev+1, r+1):
      to_update[C[x]] = x
    for c, x in to_update.items():
      if leftmost[c] >= 0:
        update(leftmost[c] + 1, -1, bit)
      leftmost[c] = x
      update(x + 1, 1, bit)
    prev = r
    #print(i, r, l)
    #print(C)
    #print([cumsum(i, bit) for i in range(1, N+1)])
    ans[i] = cumsum(r + 1, bit) - cumsum(l, bit)
    
  for a in ans:
    print(a)
  

main()