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: https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SegmentTree.py
  class SegmentTree:
      def __init__(self, data, default=0, func=max):
          """initialize the segment tree with data"""
          self._default = default
          self._func = func
          self._len = len(data)
          self._size = _size = 1 << (self._len - 1).bit_length()
  
          self.data = [default] * (2 * _size)
          self.data[_size : _size + self._len] = data
          for i in reversed(range(_size)):
              self.data[i] = func(self.data[i + i], self.data[i + i + 1])
  
      def __delitem__(self, idx):
          self[idx] = self._default
  
      def __getitem__(self, idx):
          return self.data[idx + self._size]
  
      def __setitem__(self, idx, value):
          idx += self._size
          self.data[idx] = value
          idx >>= 1
          while idx:
              self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
              idx >>= 1
  
      def __len__(self):
          return self._len
  
      def query(self, start, stop):
          """func of data[start, stop)"""
          start += self._size
          stop += self._size
  
          res_left = res_right = self._default
          while start < stop:
              if start & 1:
                  res_left = self._func(res_left, self.data[start])
                  start += 1
              if stop & 1:
                  stop -= 1
                  res_right = self._func(self.data[stop], res_right)
              start >>= 1
              stop >>= 1
  
          return self._func(res_left, res_right)
  
      def __repr__(self):
          return "SegmentTree({0})".format(self.data)
  
  
  import io
  import os
  from collections import defaultdict
  
  
  def solve(N, Q, C, LR):
      # Bucket sort queries by right endpoint
      LByR = defaultdict(list)
      for i, (l, r) in enumerate(LR):
          LByR[r].append((i, l))
  
      # Segment tree stores a 1 at position i if the ith element is the rightmost of its dupes
      segTree = SegmentTree([0] * (N + 1), 0, lambda x, y: x + y)
      lastSeen = {}
      ans = [0] * Q
      for r, x in enumerate(C):
          if x in lastSeen:
              # Clear the previous rightmost bit
              segTree[lastSeen[x]] -= 1
          # Add a new rightmost bit
          segTree[r] += 1
          lastSeen[x] = r
  
          for queryIndex, l in LByR[r]:
              ans[queryIndex] = segTree.query(l, r + 1)
  
      return "\n".join(map(str, ans))
  
  
  if __name__ == "__main__":
      input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
  
      N, Q = [int(x) for x in input().split()]
      C = [int(x) for x in input().split()]
      # 0-indexed, inclusive inclusive
      LR = [[int(x) - 1 for x in input().split()] for i in range(Q)]
      print(solve(N, Q, C, LR))
  
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"}]