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: from functools import cmp_to_key
  import sys
  
  input = sys.stdin.readline
  N, P = map(int, input().split())
  (*C,) = map(int, input().split())
  
  Q = [tuple(map(int, input().split())) for _ in range(P)]
  Q = [(i, l, r) for i, (l, r) in enumerate(Q)]
  
  block = int(N**0.5)
  
  
  def compare(a, b):
      _, la, ra = a
      _, lb, rb = b
      if (la - 1) // block != (lb - 1) // block:
          return -1 if (la - 1) // block < (lb - 1) // block else 1
      return -1 if ra < rb else 1
  
  
  Q.sort(key=cmp_to_key(compare))
  
  ans = [0] * P
  cl = cr = 0
  S = dict()
  S[C[0]] = set([0])
  cnt = 1
  for i, l, r in Q:
      l -= 1
      r -= 1
      while cl < l:
          x = C[cl]
          if x in S:
              if len(S[x]) == 1:
                  del S[x]
                  cnt -= 1
              else:
                  S[x].remove(cl)
          cl += 1
  
      while l < cl:
          x = C[cl - 1]
          if x in S:
              S[x].add(cl - 1)
          else:
              S[x] = set([cl - 1])
              cnt += 1
          cl -= 1
  
      while cr < r:
          x = C[cr + 1]
          if x in S:
              S[x].add(cr + 1)
          else:
              S[x] = set([cr + 1])
              cnt += 1
          cr += 1
  
      while r < cr:
          x = C[cr]
          if x in S:
              if len(S[x]) == 1:
                  del S[x]
                  cnt -= 1
              else:
                  S[x].remove(cr)
          cr -= 1
  
      ans[i] = cnt
  
  print("\n".join(map(str, ans)))
  
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"}]