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: def query(ind, start, end, q1, q2, s):
      if q1 > end or q2 < start:
          return 0
      if q1 <= start and q2 >= end:
          for i in segment[ind][0]:
              s.add(i)
          return 0
      mid = (start + end) // 2
      (
          query(2 * ind + 1, start, mid, q1, q2, s)
          + query(2 * ind + 2, mid + 1, end, q1, q2, s)
      )
      return len(s)
  
  
  def build(ind, start, end):
      if start == end:
          segment[ind] = [[l[start]], 1]
          return
      mid = (start + end) // 2
      build(2 * ind + 1, start, mid)
      build(2 * ind + 2, mid + 1, end)
      a = set()
      for i in segment[2 * ind + 1][0]:
          a.add(i)
      for i in segment[2 * ind + 2][0]:
          a.add(i)
  
      segment[ind] = [list(a), len(a)]
  
  
  n, m = map(int, input().split())
  l = list(map(int, input().split()))
  segment = [0] * (4 * n)
  build(0, 0, n - 1)
  
  for _ in range(m):
      a, b = map(int, input().split())
      print(query(0, 0, n - 1, a - 1, b - 1, set()))
  
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"}]