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
  
  input = sys.stdin.readline
  
  
  def solve():
      def makeBIT(numEle):
          numPow2 = 2 ** (numEle - 1).bit_length()
          data = [0] * (numPow2 + 1)
          return data, numPow2
  
      def addValue(iA, A):
          iB = iA + 1
          while iB <= numPow2:
              data[iB] += A
              iB += iB & -iB
  
      def getSum(iA):
          iB = iA + 1
          ans = 0
          while iB > 0:
              ans += data[iB]
              iB -= iB & -iB
          return ans
  
      def getRangeSum(iFr, iTo):
          return getSum(iTo) - getSum(iFr - 1)
  
      N, Q = map(int, input().split())
      cs = list(map(lambda x: int(x) - 1, input().split()))
      LRs = []
      Lss = [[] for _ in range(N)]
      for i in range(Q):
          L, R = map(int, input().split())
          L, R = L - 1, R - 1
          LRs.append((L, R))
          Lss[R].append((L, i))
  
      data, numPow2 = makeBIT(Q)
  
      anss = [0] * Q
      posRights = [-1] * N
      for R, c in enumerate(cs):
          if posRights[c] != -1:
              addValue(posRights[c], -1)
          addValue(R, 1)
          posRights[c] = R
          for L, i in Lss[R]:
              anss[i] = getRangeSum(L, R)
  
      print("\n".join(map(str, anss)))
  
  
  solve()
  
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"}]