//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
//#define ull unsigned long long
#define lll __int128
//#define double long double
#define fi first
#define se second
using namespace std;
const long long INF=1e9+5;
const long long mod=998244353,orm=3;
//const long long mod=1000000007;
const int MAXN=2000005;
const double eps=1e-6;
bool ST;
int n,Q;
int a[MAXN],b[MAXN],vst[MAXN];
int f[MAXN];
pair<int,int> p[MAXN][21];
void solve() {
	cin>>n>>Q;
	for(int i=1;i<=n;i++) cin>>a[i];
	int l=0;
	for(int i=1;i<=n;i++) {
		vst[a[i]]++;
		while(vst[a[i]]>1) vst[a[l]]--,l++;
		b[i]=l;
	}
	for(int i=1;i<=n;i++) {
		p[i][0]={1,i-1};
		if(b[i]) p[i][0]={i-b[i],b[i]-1};
	}
	for(int j=1;(1<<j)<=n;j++) {
		for(int i=1;i<=n;i++) {
			if(p[i][j-1].se&&p[p[i][j-1].se][j-1].se) p[i][j]={p[i][j-1].fi+p[p[i][j-1].se][j-1].fi,p[p[i][j-1].se][j-1].se};
		}
	}
	while(Q--) {
		int l,r,res=0;cin>>l>>r;res+=r-l;
		if(l>r) swap(l,r);
		for(int i=20;i>=0;i--) {
			if(p[r][i].se>=l) res+=p[r][i].fi,r=p[r][i].se;
		}
		res+=r-l;
		cout<<res<<"\n";
	}
}
bool ED;
signed main() {
//	cout<<(&ST-&ED)/1024.0/1024.0;
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}