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: class SegmentTree:
      def __init__(self, l):
          nb = bin(len(l))[2:]
          b = sum([int(d) for d in nb])
          if b == 1:
              self.end_leaves = pow(2, len(nb) - 1)
          else:
              self.end_leaves = pow(2, len(nb))
          self.tree = [set() for _ in range(self.end_leaves * 2)]
  
          for i in range(len(l)):
              self.tree[self.end_leaves + i].add(l[i])
  
      def union(self, a):
          if a >= self.end_leaves // 2:
              self.tree[a] = self.tree[a * 2] | self.tree[a * 2 + 1]
              return self.tree[a]
          else:
              self.tree[a] = self.union(a * 2) | self.union(a * 2 + 1)
              return self.tree[a]
  
      def query(self, l, r):
          x = l + self.end_leaves
          y = r + self.end_leaves
          tl = set()
          tr = set()
          while y - x > 1:
              if x % 2 == 1:
                  tl = tl | self.tree[x]
                  x += 1
              if y % 2 == 0:
                  tr = self.tree[y] | tr
                  y -= 1
              x >>= 1
              y >>= 1
          if y - x == 0:
              print(len(tl | tr | self.tree[x]))
          else:
              print(len(tl | tr | self.tree[x] | self.tree[y]))
  
  
  N, Q, *f = map(int, open(0).read().split())
  c = f[:N]
  lr = [f[N + i * 2 : N + i * 2 + 2] for i in range(Q)]
  st = SegmentTree(c)
  st.union(1)
  for l, r in lr:
      st.query(l - 1, r - 1)
  
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"}]