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;
struct drz {
  int base;
  vector<int> d;
  int query(int v){
    int res = 0;
    for(v += base;v > 0;v /= 2) res += d[v];
    return res;
  }
  void add(int x, int y, int val){
    for(x += base, y += base;x <= y;x /= 2, y /= 2){
      if(x % 2 == 1) d[x++] += val;
      if(y % 2 == 0) d[y--] += val;
    }
  }
  drz(int size){
    for(base = 1;base <= size;base *= 2);
    d.resize(2 * base);
  }
};
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, Q;
  cin >> n >> Q;
  vector<int> c(n), res(Q), last(n + 1);
  for(int i = 0;i < n;i++) cin >> c[i];
  vector<tuple<int, int, int>> q(Q);
  for(int i = 0;i < Q;i++){
    cin >> get<1>(q[i]) >> get<0>(q[i]);
    get<2>(q[i]) = i;
  }
  sort(q.begin(), q.end());
  fill(last.begin(), last.end(), -1);
  drz d(n + 7);
  int z = -1;
  for(auto [y, x, query] : q){
    x--;
    y--;
    while(z < y){
      z++;
      d.add(last[c[z]] + 1, z, 1);
      last[c[z]] = z;
    }
    res[query] = d.query(x);
  }
  for(int i : res) cout << i << '\n';
}
