#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::min;
using std::max;
using std::set;
using std::queue;
using std::sort;
using std::unique;
using std::vector;
using std::pair;
#define ll long long
#define db double
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define F(i,l,r) for(int i=(l);i<=(r);i++)
#define UF(i,l,r) for(int i=(l);i>=(r);i--)
#define mp std::make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls(x) x<<1
#define rs(x) x<<1|1
#define pb push_back
inline int rd(){
	int f=1,x=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return f*x;
}
const int N=1000010;
int n,m,a[N],las[N],pre[N],nxt[N],t[N],ans[N];
vector<pii>qry1[N],qry2[N];
void update(int x,int v){for(int i=x;i<=n;i+=i&-i)t[i]+=v;}
int query(int x){
    int ans=0;
    for(int i=x;i;i^=i&-i)ans+=t[i];
    return ans;
}
int main(){
    n=rd();m=rd();
    F(i,1,n){
        a[i]=rd();pre[i]=las[a[i]];
        las[a[i]]=i;
    }
    F(i,1,n)las[i]=n+1;
    UF(i,n,1){
        nxt[i]=las[a[i]];las[a[i]]=i;
    }
    F(i,1,m){
        int l=rd(),r=rd();
        if(l<=r)qry1[r].pb(mp(l,i)),ans[i]-=(l-1),ans[i]+=(r-l-1);
        else qry2[r].pb(mp(l,i)),ans[i]-=(n-l),ans[i]+=(l-r-1);
    }
    F(i,1,n){
        update(pre[i]+1,1);
        F(j,0,(int)qry1[i].size()-1)ans[qry1[i][j].se]+=query(qry1[i][j].fi);
    }
    memset(t,0,sizeof(t));
    UF(i,n,1){
        update(n+2-nxt[i],1);
        F(j,0,(int)qry2[i].size()-1)ans[qry2[i][j].se]+=query(n+1-qry2[i][j].fi);
    }
    F(i,1,m){
        cout<<ans[i]<<"\n";
    }
    return 0;
}