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 main():
      # 一点更新・一点取得の加法BIT
      class BIT:
          def __init__(self, n):
              self.n = n
              self.maxbit = 2 ** (len(bin(n)) - 3)
              self.bit = [0] * (n + 1)
              self.allsum = 0
  
          # 初期化する
          def make_bit(self, a):
              n, bit = self.n, self.bit
              for i, j in enumerate(a):
                  x = i + 1
                  self.allsum += j
                  while x < n + 1:
                      bit[x] += j
                      x += x & (-x)
  
          # 位置iに値vを足す
          def add(self, i, v):
              x, n, bit = i + 1, self.n, self.bit
              self.allsum += v
              while x < n + 1:
                  bit[x] += v
                  x += x & (-x)
  
          # 位置0からiまでの和(sum(bit[:i]))を計算する
          def sum(self, i):
              ret, x, bit = 0, i, self.bit
              while x > 0:
                  ret += bit[x]
                  x -= x & (-x)
              return ret
  
          # 位置iからjまでの和(sum(bit[i:j]))を計算する
          def sum_range(self, i, j):
              return self.sum(j) - self.sum(i)
  
          # 和がw以上となる最小のインデックスを求める
          def lowerbound(self, w):
              if w <= 0:
                  return 0
              x, k, n, bit = 0, self.maxbit, self.n, self.bit
              while k:
                  if x + k <= n and bit[x + k] < w:
                      w -= bit[x + k]
                      x += k
                  k //= 2
              return x
  
      n, q = map(int, input().split())
      c = list(map(int, input().split()))
      lastappend = [-1] * n
      lr = [list(map(int, input().split())) for _ in [0] * q]
      ilr = [(i, l - 1, r - 1) for i, (l, r) in enumerate(lr)]
      ilr.sort(key=lambda x: (x[2], x[1], x[0]))
      bit = BIT(n)
      ans = [-1] * q
      r_now = -1
      for i, l, r in ilr:
          if r > r_now:
              for j in range(r_now + 1, r + 1):
                  last = lastappend[c[j]]
                  if last != -1:
                      bit.add(last, -1)
                  lastappend[c[j]] = j
                  bit.add(j, 1)
              r_now = r
          ans[i] = bit.sum_range(l, r + 1)
      for i in ans:
          print(i)
  
  
  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"}]