output_description: Print Q lines. The i-th line should contain the response to the i-th query.
  
  * * *
input_description: 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
attempt: N, Q = map(int, input().split())
  N = 5 * 10**5
  value_to_index = [[] for i in range(N)]
  
  C = list(map(int, input().split()))
  
  for i, v in reversed(list(enumerate(C))):
      value_to_index[v - 1].append(i)
  LR = [list(map(int, input().split())) + [i] for i in range(Q)]
  LR.sort()
  
  # セグ作成
  segtree = [[0] * N.bit_length() for i in range(N.bit_length())]
  for num, arr in enumerate(value_to_index):
      if arr:
          v = arr[-1]
          for i in range(len(segtree)):
              p2 = 2**i
              segtree[i][v // p2] += 1
  
  
  # セグ取得
  def seg_range(l, r):
      r += 1
      ans = []
      tmp = 1
      # 大きくしていくゾーン
      while True:
          while l % (tmp * 2) == 0 and tmp <= r:
              tmp *= 2
          if l + tmp <= r:
              ans.append((tmp.bit_length() - 1, l // tmp))
              l += tmp
          else:
              break
      # 小さくしていくゾーン
      tmp //= 2
      while tmp > 0:
          if l + tmp <= r:
              ans.append((tmp.bit_length() - 1, l // tmp))
              l += tmp
          tmp //= 2
      return ans
  
  
  tmp = 0
  ans = [0] * N
  for l, r, idx in LR:
      while tmp < l - 1:
          v = C[tmp] - 1
          tmp += 1
          old = value_to_index[v].pop()
          if value_to_index[v]:
              new = value_to_index[v][-1]
              for i in range(len(segtree)):
                  p2 = 2**i
                  segtree[i][new // p2] += 1
          for i in range(len(segtree)):
              p2 = 2**i
              segtree[i][old // p2] -= 1
      ans[idx] = sum([segtree[i][j] for i, j in seg_range(l - 1, r - 1)])
  print(*ans[:Q], sep="\n")
  
problem_description: Statement
  
  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?
samples: [{"input": "4 3\n    1 2 1 3\n    1 3\n    2 4\n    3 3", "output": "2\n    3\n    1\n    \n\n  * The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 \\- two different colors.\n  * The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 \\- three different colors.\n  * The 3-rd ball from the left has the color 1 \\- just one color.\n\n* * *"}, {"input": "10 10\n    2 5 6 5 2 1 7 9 7 2\n    5 5\n    2 4\n    6 7\n    2 2\n    7 8\n    7 9\n    1 8\n    6 9\n    8 10\n    6 8", "output": "1\n    2\n    2\n    1\n    2\n    2\n    6\n    3\n    3\n    3"}]