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: import sys
  import io, os
  
  input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
  from operator import itemgetter
  
  N, Q = map(int, input().split())
  C = [0] + list(map(int, input().split()))
  
  QU = [list(map(int, input().split())) + [i] for i in range(Q)]
  
  
  QU.sort(key=itemgetter(0))
  
  
  # BIT(BIT-indexed tree)
  
  LEN = N + 3
  
  BIT = [0] * (LEN + 1)  # 1-indexedなtree
  
  
  def update(v, w):  # index vにwを加える
      while v <= LEN:
          BIT[v] += w
          v += v & (-v)  # 自分を含む大きなノードへ. たとえばv=3→v=4
  
  
  def getvalue(v):  # [1,v]の区間の和を求める
      ANS = 0
      while v != 0:
          ANS += BIT[v]
          v -= v & (-v)  # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
      return ANS
  
  
  NUM = [[] for i in range(N + 1)]
  for i, c in enumerate(C):
      if i == 0:
          continue
      if NUM[c] == []:
          update(i, 1)
      NUM[c].append(i)
  
  NUMIND = [0] * (N + 1)
  
  ANS = [-1] * Q
  
  ia = 1
  
  for x, y, ind in QU:
  
      while ia != x:
          update(NUM[C[ia]][NUMIND[C[ia]]], -1)
          NUMIND[C[ia]] += 1
          if NUMIND[C[ia]] < len(NUM[C[ia]]):
              update(NUM[C[ia]][NUMIND[C[ia]]], 1)
          ia += 1
  
      # print(x,y,ind)
      # print([getvalue(i) for i in range(1,N+1)])
      ANS[ind] = getvalue(y)
  
  sys.stdout.write(" ".join(map(str, ANS)) + "\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"}]