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>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

const int N = 500005;

// [1, n]
int bit[N], n, q;

int sum(int i) {
  int s = 0;
  while (i > 0) {
    s += bit[i];
    i -= i & -i;
  }
  return s;
}

void add(int i, int x) {
  while (i <= n) {
    bit[i] += x;
    i += i & -i;
  }
}

int main() {
  cin >> n >> q;
  vector<int> c(n);
  rep(i, n) cin >> c[i];
  rep(i, n) c[i]--;
  vector<pair<P, int>> query(q);
  rep(i, q) {
    int l, r;
    cin >> l >> r;
    query[i] = make_pair(make_pair(r, l), i);
  }
  sort(query.begin(), query.end());

  vector<int> gb(n, -1);
  rep(i, n+1) bit[i] = 0;
  vector<int> ans(q);

  int qi = 0;
  rep(i, n) {
    if (gb[c[i]] != -1) add(gb[c[i]], -1);
    gb[c[i]] = i+1;
    add(i+1, 1);
    while (query[qi].first.first == i+1) {
      int ai = query[qi].second;
      int l = query[qi].first.second;
      int r = query[qi].first.first;
      ans[ai] = sum(r) - sum(l-1);
      qi++;
    }
  }

  rep(i, q) cout << ans[i] << endl;
  return 0;
}