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;
using VI = vector<int>;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);

  int n, q; cin >> n >> q;
  VI c(n); rep(i, n) cin >> c[i];
  vector<pair<int, int>> lr(q); rep(i, q) cin >> lr[i].first >> lr[i].second;
  rep(i, q) lr[i].first--;

  const int sq = 700;
  vector<tuple<int, int, int>> lri(q);
  rep(i, q) lri[i] = make_tuple(lr[i].first / sq, lr[i].second, i);
  sort(lri.begin(), lri.end());

  VI ans(q);

  VI cnt(n+1);
  int prev = -1;
  int lx, rx;
  int sum = 0;
  for (auto [ls, r, i] : lri) {
    if (ls != prev) {
      fill(cnt.begin(), cnt.end(), 0);
      lx = rx = r;
      prev = ls;
      sum = 0;
    }
    int l = lr[i].first;
    assert(r == lr[i].second); assert(rx <= r);
    int cx;
    while (lx > l) if (cnt[cx=c[--lx]]++ == 0) sum += 1;
    while (lx < l) if (--cnt[c[lx++]] == 0) sum -= 1;
    while (rx < r) if (cnt[cx=c[rx++]]++ == 0) sum += 1;
    ans[i] = sum;
  }
  rep(i, q) cout << ans[i] << "\n";
}
