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

template <typename T>
class BIT {
  int n;
  vector<T> bit;
public:
  BIT(int _n) {
    n = _n;
    bit = vector<T>(n+1,(T)0);
  }
  T sum(int i) {
    T s = 0;
    while(i > 0){
    s += bit[i];
    i -= i & -i;
  }
  return s;
  }
  void add(int i, T x) {
    while(i <= n){
    bit[i] += x;
    i += i & -i;
    }
  }
};

int main(){
  int n, q;
  cin >> n >> q;
  int c[n];
  rep(i,n) {
    cin >> c[i];
    c[i]--;
  }
  int l[q], r[q], ord[q];
  rep(i,q) {
    cin >> l[i] >> r[i];
    l[i]--; r[i]--;
    ord[i] = i;
  }
  sort(ord,ord+q,[&](int a, int b){return r[a] < r[b];});
  vector<int> last(n,-1);
  BIT<int> bit(n+1);
  int ans[q];
  int pos = 0;
  rep(i,q) {
    while(pos <= r[ord[i]]) {
      if(last[c[pos]] != -1) bit.add(last[c[pos]],-1);
      last[c[pos]] = pos+1;
      bit.add(pos+1,1);
      pos++;
    }
    ans[ord[i]] = bit.sum(r[ord[i]]+1) - bit.sum(l[ord[i]]);
  }
  for(auto x : ans) cout << x << endl;
  return 0;
}
