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;

typedef long long ll;
typedef pair <int , int> pii;
typedef long double ld;

const int N = 5e5+10 , mod = 1e9+7;

vector <int> col[N];
vector <pii> v[N];
int c[N] , fen[N] , ans[N] , cur[N];

void add(int x , int val){
   for( ; x < N ; x += x & -x)
      fen[x] += val;
}

int get(int x){
   int ret = 0;
   for( ; x ; x -= x & -x)
      ret += fen[x];
   return ret;
}

int32_t main(){
   ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
   int n , q;
   cin >> n >> q;
   for(int i = 1 ; i <= n ; i++){
      cin >> c[i];
      if(col[c[i]].empty())
         add(i , 1);
      col[c[i]].push_back(i);
   }
   for(int i = 0 ; i < q ; i++){
      int l , r;
      cin >> l >> r;
      v[l].push_back({r , i});
   }
   for(int i = 1 ; i <= n ; i++){
      for(pii x : v[i])
         ans[x.second] = get(x.first);
      add(i , -1);
      cur[c[i]]++;
      if(cur[c[i]] < col[c[i]].size()){
         add(col[c[i]][cur[c[i]]] , 1);
      }
   }
   for(int i = 0 ; i < q ; i++)
      cout << ans[i] << "\n";
   return 0;
}
