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,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=2e6+5;
int n,m,a[N];
int used[N],ans[N];
struct ask{
    int l,r,id;
}asks[N];
bool cmp(ask a,ask b) {
    return a.r<b.r;
}
int t[N];
int lowbit(int x) {return x&(-x);}
void modify(int x,int val) {
    for(;x<=n;x+=lowbit(x)) t[x]+=val;
}
int query(int x) {
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=t[x];
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&a[i]);
    rep(i,1,m) asks[i].id=i,scanf("%d%d",&asks[i].l,&asks[i].r);
    sort(asks+1,asks+m+1,cmp);
    int now=1;
    rep(i,1,m) {
        rep(j,now,asks[i].r) {
            if(used[a[j]]) modify(used[a[j]],-1);
            modify(j,1);
            used[a[j]]=j;
        }
        ans[asks[i].id]=query(asks[i].r)-query(asks[i].l-1);
        now=asks[i].r+1;
    }
    rep(i,1,m) printf("%d\n",ans[i]);
    return 0;
}