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?

Constraints

* 1\leq N,Q \leq 5 \times 10^5
* 1\leq c_i \leq N
* 1\leq l_i \leq r_i \leq N
* All values in input are integers.

Input

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


Output

Print Q lines. The i-th line should contain the response to the i-th query.

Examples

Input

4 3
1 2 1 3
1 3
2 4
3 3


Output

2
3
1


Input

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8


Output

1
2
2
1
2
2
6
3
3
3
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, q;
  cin >> n >> q;
  
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> c.at(i);
    c.at(i)--;
  }
  
  vector<vector<pair<int, int>>> p(n);
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    l--; r--;
    p.at(l).emplace_back(r, i);
  }
  
  vector<vector<int>> same(n);
  vector<int> prev(n, -1);
  for (int i = 0; i < n; i++) {
    if (prev.at(c.at(i)) != -1) {
      same.at(prev.at(c.at(i))).push_back(i);
    }
    prev.at(c.at(i)) = i;
  }
  
  vector<int> ans(q), bit(n + 1);
  for (int i = n - 1; i >= 0; i--) {
    for (int x : same.at(i)) {
      int k = x + 1;
      while (k <= n) {
        bit.at(k)++;
        k += k & -k;
      }
    }
    for (auto query : p.at(i)) {
      int r = query.first, index = query.second, s = 0, k = r + 1;
      while (k) {
        s += bit.at(k);
        k -= k & -k;
      }
      ans.at(index) = r - i + 1 - s;
    }
  }
  
  for (int i = 0; i < q; i++) {
    cout << ans.at(i) << "\n";
  }
}
