#include<bits/stdc++.h>
using namespace std;
int n,q,a[2010],l,r,ans,ans2,t[2010],t2[2010];
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)  cin>>a[i];
	while(q--)
	{
		cin>>l>>r;
		memset(t,0,sizeof(t));memset(t2,0,sizeof(t2));
		ans=ans2=r-l+1;
		for(int i=l;i<=r;i++){t[a[i]]++;t2[a[i]]++;}
		for(int i=l;i<=r;i++)
		{
			if(t[a[i]]>1){ans--;t[a[i]]--;}
			else  break;
		}
		for(int i=r;i>=l;i--)
		{
			if(t[a[i]]>1){ans--;t[a[i]]--;}
			else  break;
		}
		
		for(int i=r;i>=l;i--)
		{
			if(t2[a[i]]>1){ans2--;t2[a[i]]--;}
			else  break;
		}
		for(int i=l;i<=r;i++)
		{
			if(t2[a[i]]>1){ans2--;t2[a[i]]--;}
			else  break;
		}
		cout<<min(ans,ans2)<<endl; 
	}
	return 0;
}