#include <iostream>
using namespace std;

int *data,*same,*cur;
int appear[2000001];
void getSame(int n)
{
	same[n-1]=1;appear[1000000+data[n-1]]=n-1;cur[n-1]=-1;
	for(int i=n-2;i>=0;i--)
	{
		if(appear[1000000+data[i]]==0)
		{
			same[i]=same[i+1]+1;
			appear[1000000+data[i]] = i;
			cur[i] = cur[i+1];
		}
		else
		{
			int tem = appear[1000000+data[i]];
			if(tem<=(i+same[i+1]))
			{
				same[i]=tem-i;
				cur[i] = i+1;
			}
			else
			{
				same[i]=same[i+1]+1;
				cur[i] = cur[i+1];
			}
			appear[1000000+data[i]] = i;
		}
	}

	//cout<<"the same: ";
	//for(int i=0;i<n;i++)
	//	cout<<same[i]<<" ";
	//cout<<endl;

}
int main()
{
	int n,m;
	cin>>n>>m;
	data = new int[n];
	same = new int[n];
	cur  = new int[n];
	for(int i=0;i<n;i++)
	{
		cin>>data[i];
	}
	getSame(n);
	for(int i=0;i<m;i++)
	{
		int s,t;
		cin>>s>>t;
		int max=0;
		for(int j=s;j<=t;j=cur[j])
		{
			if(j==-1)break;
			int temp = same[j];
			if(temp>(t-j+1))
			{
				temp = t-j+1;
				if(temp>max)
				{
					max = temp;break;
				}
			}
			if(temp>max)max=temp;
		}
		cout<<max<<endl;
	}
	//getchar();
	return 0;
}