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 Set(a,b) memset(a,b,sizeof(a))
template<class T>inline void init(T&x){
  x=0;char ch=getchar();bool f=0;
  for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') f=1;
  for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
  if(f) x=-x;
  return;
}
typedef long long ll;
typedef double db;
const int mod=998244353,G=3,phi=998244352;
const int N=5e5+10;
int C[N];
int n,m;
int id[N],l[N],r[N];
int tr[N],ans[N],ls[N];
#define lowbit(a) ((a)&(-a))
inline void Add(int p,int x){for(;p<=n;p+=lowbit(p)) tr[p]+=x;}
inline int Query(int p){int s=0;for(;p;p-=lowbit(p)) s+=tr[p];return s;}
inline bool cmp(int x,int y){return r[x]<r[y];}
int main(){
  init(n),init(m);
  for(int i=1;i<=n;++i) init(C[i]);
  for(int i=1;i<=m;++i) init(l[i]),init(r[i]),id[i]=i;
  sort(id+1,id+1+m,cmp);
  int nowr=0;
  for(int i=1;i<=m;++i) {
    int I=id[i];
    while(nowr<r[I]) {
      ++nowr;int c=C[nowr];
      if(ls[c]) Add(ls[c],-1);
      Add(nowr,1);ls[c]=nowr;
    }
    ans[I]=Query(r[I])-Query(l[I]-1);
  }
  for(int i=1;i<=m;++i) cout<<ans[i]<<endl;
}
