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 sys import stdin
  
  
  class BIT:
      def __init__(self, n):
          self.data = [0] * (n + 10)
  
      def upd(self, pos, val=1):
          pos += 1
          while pos < len(self.data):
              self.data[pos] += val
              pos += pos & -pos
  
      def get(self, pos):
          ans = 0
          pos += 1
          while pos > 0:
              ans += self.data[pos]
              pos -= pos & -pos
          return ans
  
      def get_range(self, l, r):
          return self.get(r) - self.get(l - 1)
  
  
  def main():
      n, q = map(int, stdin.readline().split())
      color = list(map(int, stdin.readline().split()))
  
      queries = []
      for i in range(q):
          l, r = map(int, stdin.readline().split())
          queries.append((l, r, i))
      queries.sort(key=lambda val: val[1])
  
      ans = [0] * q
      prev_pos = [0] * (n + 1)
      bit = BIT(n + 1)
  
      f = 0
      for cur_pos, color in enumerate(color, 1):
          bit.upd(prev_pos[color], -1)
          bit.upd(cur_pos, 1)
          prev_pos[color] = cur_pos
  
          while f < q and queries[f][1] == cur_pos:
              ans[queries[f][2]] = bit.get_range(queries[f][0], queries[f][1])
              f += 1
      print("\n".join(map(str, ans)))
  
  
  main()
  
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"}]