#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int inf=5e16L;
int n,q,a[N],f[N][2],kong[N],t[N];
void work()
{
	int l,r,ans=0;
	cin>>l>>r;
	if(l>r)swap(l,r);
	int last=l;
	for(int i=l;i<=r;i++)
	{
		if(t[a[i]])
		{
			int tmp=i-last+1-1;
			if(t[a[i]]>=last)tmp--;
			if(last>l&&a[last-1]!=a[i])++tmp;
			ans+=tmp;
			for(int j=last;j<=i;j++)t[a[j]]=0;
//			cout<<"cnm: "<<i<<' '<<last<<' '<<tmp<<'\n';
			last=i+1;
		}
		t[a[i]]=i;
	}
	if(last!=r+1)
	{
		ans+=r-last+1;
		if(last==l)ans--;
	}
//	cout<<"cnm: "<<l<<' '<<r<<' '<<last<<'\n';
	for(int i=l;i<=r;i++)t[a[i]]=0;
	ans+=r-l;
	cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=q;i++)work();
	return 0;
}
/*
5 1
1 1 4 2 1 
1 5

5 1
1 1 3 5 5
1 4

5 5
5 5 1 1 4 
3 5
2 5
2 4
1 5
1 5

5 1
1 4 3 5 4 
1 5

5 1
1 2 3 1 2
1 5
*/