#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[300005],ans[300005],bit[300005];
map <int,int> mp;
vector <pair<int,int>> ve[300005];
void UPDATE(int i, int v)
{
    while (i<=n) bit[i]+=v,i+=i&(-i);
    return;
}
int GET(int l, int r)
{
    l--;
    int resl=0,resr=0;
    while (l>0) resl+=bit[l],l-=l&(-l);
    while (r>0) resr+=bit[r],r-=r&(-r);
    return resr-resl;
}
signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=q;i++) 
    {
        int l,r;
        cin>>l>>r;
        ve[r].push_back({l,i});
    }
    for (int i=1;i<=n;i++)
    {
        if (!mp[a[i]]) mp[a[i]]=i,UPDATE(i,1);
        else UPDATE(i,1),UPDATE(mp[a[i]],-1),mp[a[i]]=i;
        for (pair <int,int> p : ve[i])
        {
            int l=p.first,idx=p.second;
            ans[idx]=GET(l,i);
        }
    }
    for (int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}