#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define     bit_1(a)       __builtin_popcount(a)
#define     ull            unsigned long long
#define     ll             long long
#define     u              unsigned
#define     pb             push_back
#define     pf             push_front
#define     mpr            make_pair
#define     ins            insert
#define     ff             first
#define     ss             second
#define     vi             vector<int>
#define     vl             vector<ll>
#define     vstr           vector<string>
#define     si             set<int>
#define     sl             set<ll>
#define     li             list<int>
#define     pii            pair<int,int>
#define     pll            pair<ll,ll>
#define     mii            map<int,int>
#define     mll            map<ll,ll>
#define     ma             INT_MAX
#define     mi             INT_MIN
#define     mod            1000000007
#define     pi             3.14159265359
#define     e              2.71828182846
#define     inf            1000000000000000LL
#define     all(x)         x.begin(), x.end()
#define     lb(a,b,c)      lower_bound(a,a+b,c)-a
#define     ub(a,b,c)      upper_bound(a,a+b,c)-a
#define     lbv(a,c)       lower_bound(all(a),c)-a.begin()
#define     ubv(a,c)       upper_bound(all(a),c)-a.begin()
#define     srt1(a,b)      sort(a,a+b)
#define     srt2(a,b)      sort(a,a+b,greater<int>())
#define     gcd(a,b)       __gcd(a,b)
#define     lcm(a,b)       (a*(b/gcd(a,b)))
#define     harmonic(n)    0.57721566490153286l+log(n)
#define     mem(a, b)      memset(a, b, sizeof(a))
#define     orderset1      tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define     orderset2      tree<int,null_type,greater<int>,rb_tree_tag,tree_order_statistics_node_update>

///s.lower_bound(a),s.upper_bound(a), for set
///nCr(x, y) = nCr(x-1, y-1) + nCr(x-1, y)
///factorial digit   ((n * log10(n / e) +log10(2 * pi * n) /2.0));
/// lcm(a,b)=a/gcd(a,b)*b (handle overflow)

bool sortinrev1(const pair<int,int>&a,const pair<int,int>&b)
{
    //return (a.first > b.first);
    if(a.first==b.first)return (a.second>b.second);
    else return (a.first > b.first);
}
bool sortinrev2(const pair<int,int>&a,const pair<int,int>&b)
{
    //return (a.first > b.first);
    if(a.first==b.first)return (a.second<b.second);
    else return (a.first > b.first);
}
int fx[]={1,-1,0,0};
int fy[]={0,0,1,-1};

const int N=500005;
int block=800,ans[N];
int freq[N];

struct node{
    int l,r,index;
}Q[N];

bool comp(node a,node b)
{
    if(a.l/block!=b.l/block)
        return a.l/block<b.l/block;
    else return a.r<b.r;
}

int main()
{
    /*int n;
    cin>>n;
    if(n>=30)cout<<"Yes\n";
    else cout<<"No\n";*/
    /*mll mp;
    ll n,d,xi,yi,ans=0;
    cin>>n>>d;
    while(n--){
        cin>>xi>>yi;
        ll p=ceil(sqrt((xi*xi)+(yi*yi)));
        if(p<=d)ans++;
    }
    cout<<ans<<endl;*/
    /*int n,ans=0;
    string str;
    cin>>n>>str;
    int w=count(str.begin(),str.end(),'W');
    int r=count(str.begin(),str.end(),'R');
    if(w==0){
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<r;i++){
        if(str[i]=='W')ans++;
    }
    cout<<ans<<endl;*/
    int n,q,cnt=0;
    scanf("%d %d",&n,&q);
    int ar[n+5];
    for(int i=0;i<n;i++)scanf("%d",&ar[i]);
    for(int i=0;i<q;i++){
        scanf("%d %d",&Q[i].l,&Q[i].r);
        Q[i].l--;
        Q[i].r--;
        Q[i].index=i;
    }
    sort(Q,Q+q,comp);
    int ML=0,MR=-1;
    for(int i=0;i<q;i++){
        int L=Q[i].l;
        int R=Q[i].r;
        while(ML>L){
            ML--;
            freq[ar[ML]]++;
            if(freq[ar[ML]]==1)cnt++;
        }
        while(MR<R){
            MR++;
            freq[ar[MR]]++;
            if(freq[ar[MR]]==1)cnt++;
        }
        while(ML<L){
            freq[ar[ML]]--;
            if(freq[ar[ML]]==0)cnt--;
            ML++;
        }
        while(MR>R){
            freq[ar[MR]]--;
            if(freq[ar[MR]]==0)cnt--;
            MR--;
        }
        ans[Q[i].index]=cnt;
    }
    for(int i=0;i<q;i++)
        printf("%d\n",ans[i]);
}



Measured memory_bytes: 15420