#include <iostream>
using namespace std;
struct node{//Node and the values i want to store
int value;
int prefix;
int suffix;
int freq;
};
void build(int n,int start,int end, int tree[],node arr[])
{
/*This build function follows typical segment tree build for answering Range Maximum Query*/
if(start==end)
tree[n]=arr[start].freq;
else
{
int mid=(start+end)/2;
build(2*n+1,start,mid,tree,arr);
build(2*n+2,mid+1,end,tree,arr);
tree[n]= max(tree[2*n+1],tree[2*n+2]);
}
}
int query (int n, int start, int end, int l, int r, int tree[],node arr[])
{
/*The query function is also typical one answering simple RMQ*/
if(l>r or start>end) return 0;
if(start>r or end<l) return 0;
else if(start>=l and end<=r)//Changing condition here to "if(start==end) removes WA, but gives TLE."
{
//cout<<"tree["<<n<<"] is "<<tree[n]<<endl;
return tree[n];
}
else
{
int mid=(start+end)/2,p=0,q=0;
//if(r>=start)
p=query(2*n+1,start,mid,l,r,tree,arr);
//if(l<=end)
q=query(2*n+2,mid+1,end,l,r,tree,arr);
return max(p,q);
}
}
int main() {
// your code goes here
ios_base::sync_with_stdio(0);//Fast input, Output
cin.tie(NULL);
cout.tie(NULL);
while(true)
{
int n,q;
cin>>n;
if(n==0)break;
cin>>q;
node arr[n];
int tree2[4*n+4];
int i,j,k;
for(i=0;i<n;i++)
{
cin>>arr[i].value;//An attempt to take input has been made here.
}
arr[0].prefix=0;
arr[n-1].suffix=n-1;
arr[0].freq=1;
for(i=1,j=n-2;i<n && j>=0;i++,j--)//The variable names are self-explanatory for the funtion.
{
if(arr[i].value==arr[i-1].value)
arr[i].prefix=arr[i-1].prefix;
else
arr[i].prefix=i;
if(arr[i].value==arr[i-1].value)
arr[i].freq=arr[i-1].freq+1;
else
arr[i].freq=1;
if(arr[j].value==arr[j+1].value)
arr[j].suffix=arr[j+1].suffix;
else
arr[j].suffix=j;
}
/*Below 4 loops were used in debugging, to check if things are working correctly till here.*/
//for(i=0;i<n;i++)cout<<arr[i].value<<" ";cout<<endl;
//for(i=0;i<n;i++)cout<<arr[i].prefix<<" ";cout<<endl;
//for(i=0;i<n;i++)cout<<arr[i].suffix<<" ";cout<<endl;
//for(i=0;i<n;i++)cout<<arr[i].freq<<" ";cout<<endl;
build(0,0,n-1,tree2,arr);//Build function to build the tree.
// for(i=0;i<2*n+4;i++)cout<<tree2[i]<<" ";cout<<endl;
while(q--)
{
int a,b;
cin>>a>>b;
a--,b--;
if(arr[a].prefix==arr[b].prefix)//If the range has a single block, eg-{1,1,1,1}
cout<<b-a+1<<"\n";
else if(arr[a].suffix+1==arr[b].prefix)//If range has only 2 blocks, eg- {1,1,1,2,2,2,2}
cout<<max(arr[a].suffix-a+1,b-arr[b].prefix+1)<<"\n";
else
{
int ans=max(arr[a].suffix-a+1,b-arr[b].prefix+1);
//cout<<"Ans and initial+final skip are "<<ans<<" "<<arr[a].suffix+1<<" "<<arr[b].prefix-1<<"\n";
//cout<<"The 2 choices were "<<arr[a].suffix-a+1<<" "<<b-arr[b].prefix+1<<"\n";
ans=max(ans,query(0,0,n-1,arr[a].suffix+1,arr[b].prefix-1,tree2,arr));
ans=max(ans,1);
cout<<ans<<"\n";
}
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IG5vZGV7Ly9Ob2RlIGFuZCB0aGUgdmFsdWVzIGkgd2FudCB0byBzdG9yZQogICAgaW50IHZhbHVlOwogICAgaW50IHByZWZpeDsKICAgIGludCBzdWZmaXg7CiAgICBpbnQgZnJlcTsKfTsKCnZvaWQgYnVpbGQoaW50IG4saW50IHN0YXJ0LGludCBlbmQsIGludCB0cmVlW10sbm9kZSBhcnJbXSkKewogICAgLypUaGlzIGJ1aWxkIGZ1bmN0aW9uIGZvbGxvd3MgdHlwaWNhbCBzZWdtZW50IHRyZWUgYnVpbGQgZm9yIGFuc3dlcmluZyBSYW5nZSBNYXhpbXVtIFF1ZXJ5Ki8KICAgIGlmKHN0YXJ0PT1lbmQpCiAgICAgICAgdHJlZVtuXT1hcnJbc3RhcnRdLmZyZXE7CiAgICBlbHNlCiAgICB7CiAgICAgICAgaW50IG1pZD0oc3RhcnQrZW5kKS8yOwogICAgICAgIGJ1aWxkKDIqbisxLHN0YXJ0LG1pZCx0cmVlLGFycik7CiAgICAgICAgYnVpbGQoMipuKzIsbWlkKzEsZW5kLHRyZWUsYXJyKTsKICAgICAgICB0cmVlW25dPSBtYXgodHJlZVsyKm4rMV0sdHJlZVsyKm4rMl0pOwogICAgfQp9CmludCBxdWVyeSAoaW50IG4sIGludCBzdGFydCwgaW50IGVuZCwgaW50IGwsIGludCByLCBpbnQgdHJlZVtdLG5vZGUgYXJyW10pCnsKICAgIC8qVGhlIHF1ZXJ5IGZ1bmN0aW9uIGlzIGFsc28gdHlwaWNhbCBvbmUgYW5zd2VyaW5nIHNpbXBsZSBSTVEqLwogICAgaWYobD5yIG9yIHN0YXJ0PmVuZCkgcmV0dXJuIDA7CiAgICBpZihzdGFydD5yIG9yIGVuZDxsKSByZXR1cm4gMDsKICAgIGVsc2UgaWYoc3RhcnQ+PWwgYW5kIGVuZDw9cikvL0NoYW5naW5nIGNvbmRpdGlvbiBoZXJlIHRvICJpZihzdGFydD09ZW5kKSByZW1vdmVzIFdBLCBidXQgZ2l2ZXMgVExFLiIKICAgIHsKICAgICAgICAvL2NvdXQ8PCJ0cmVlWyI8PG48PCJdIGlzICI8PHRyZWVbbl08PGVuZGw7CiAgICAgICAgcmV0dXJuIHRyZWVbbl07CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgaW50IG1pZD0oc3RhcnQrZW5kKS8yLHA9MCxxPTA7CiAgICAgICAgLy9pZihyPj1zdGFydCkKICAgICAgICBwPXF1ZXJ5KDIqbisxLHN0YXJ0LG1pZCxsLHIsdHJlZSxhcnIpOwogICAgICAgIC8vaWYobDw9ZW5kKQogICAgICAgIHE9cXVlcnkoMipuKzIsbWlkKzEsZW5kLGwscix0cmVlLGFycik7CiAgICAgICAgcmV0dXJuIG1heChwLHEpOwogICAgfQp9CmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsvL0Zhc3QgaW5wdXQsIE91dHB1dAoJY2luLnRpZShOVUxMKTsKCWNvdXQudGllKE5VTEwpOwoJd2hpbGUodHJ1ZSkKCXsKCSAgICBpbnQgbixxOwoJICAgIGNpbj4+bjsKCSAgICBpZihuPT0wKWJyZWFrOwoJICAgIGNpbj4+cTsKCSAgICBub2RlIGFycltuXTsKCSAgICBpbnQgdHJlZTJbNCpuKzRdOwoJICAgIGludCBpLGosazsKCSAgICBmb3IoaT0wO2k8bjtpKyspCgkgICAgewoJICAgICAgICBjaW4+PmFycltpXS52YWx1ZTsvL0FuIGF0dGVtcHQgdG8gdGFrZSBpbnB1dCBoYXMgYmVlbiBtYWRlIGhlcmUuCgkgICAgfQoJICAgIGFyclswXS5wcmVmaXg9MDsKCSAgICBhcnJbbi0xXS5zdWZmaXg9bi0xOwoJICAgIGFyclswXS5mcmVxPTE7CgkgICAgZm9yKGk9MSxqPW4tMjtpPG4gJiYgaj49MDtpKyssai0tKS8vVGhlIHZhcmlhYmxlIG5hbWVzIGFyZSBzZWxmLWV4cGxhbmF0b3J5IGZvciB0aGUgZnVudGlvbi4KCSAgICB7CgkgICAgICAgIGlmKGFycltpXS52YWx1ZT09YXJyW2ktMV0udmFsdWUpCgkgICAgICAgICAgICBhcnJbaV0ucHJlZml4PWFycltpLTFdLnByZWZpeDsKCSAgICAgICAgZWxzZQoJICAgICAgICAgICAgYXJyW2ldLnByZWZpeD1pOwoJICAgICAgIGlmKGFycltpXS52YWx1ZT09YXJyW2ktMV0udmFsdWUpCgkgICAgICAgICAgICBhcnJbaV0uZnJlcT1hcnJbaS0xXS5mcmVxKzE7CgkgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIGFycltpXS5mcmVxPTE7CSAgCiAgICAgICAgICAgICBpZihhcnJbal0udmFsdWU9PWFycltqKzFdLnZhbHVlKQoJICAgICAgICAgICAgYXJyW2pdLnN1ZmZpeD1hcnJbaisxXS5zdWZmaXg7CgkgICAgICAgIGVsc2UKCSAgICAgICAgICAgIGFycltqXS5zdWZmaXg9ajsKICAgICAgICAgICAgCgkgICAgfQoJICAgIC8qQmVsb3cgNCBsb29wcyB3ZXJlIHVzZWQgaW4gZGVidWdnaW5nLCB0byBjaGVjayBpZiB0aGluZ3MgYXJlIHdvcmtpbmcgY29ycmVjdGx5IHRpbGwgaGVyZS4qLwoJICAgIC8vZm9yKGk9MDtpPG47aSsrKWNvdXQ8PGFycltpXS52YWx1ZTw8IiAiO2NvdXQ8PGVuZGw7CgkgICAgLy9mb3IoaT0wO2k8bjtpKyspY291dDw8YXJyW2ldLnByZWZpeDw8IiAiO2NvdXQ8PGVuZGw7CgkgICAgLy9mb3IoaT0wO2k8bjtpKyspY291dDw8YXJyW2ldLnN1ZmZpeDw8IiAiO2NvdXQ8PGVuZGw7CgkgICAgLy9mb3IoaT0wO2k8bjtpKyspY291dDw8YXJyW2ldLmZyZXE8PCIgIjtjb3V0PDxlbmRsOwoJICAgIAoJICAgIAoJICAgIGJ1aWxkKDAsMCxuLTEsdHJlZTIsYXJyKTsvL0J1aWxkIGZ1bmN0aW9uIHRvIGJ1aWxkIHRoZSB0cmVlLgoJICAgIAoJICAgIAoJICAgLy8gZm9yKGk9MDtpPDIqbis0O2krKyljb3V0PDx0cmVlMltpXTw8IiAiO2NvdXQ8PGVuZGw7CgkgICAgd2hpbGUocS0tKQoJICAgIHsKCSAgICAgICAgaW50IGEsYjsKCSAgICAgICAgY2luPj5hPj5iOwoJICAgICAgICBhLS0sYi0tOwoJICAgICAgICBpZihhcnJbYV0ucHJlZml4PT1hcnJbYl0ucHJlZml4KS8vSWYgdGhlIHJhbmdlIGhhcyBhIHNpbmdsZSBibG9jaywgZWctezEsMSwxLDF9CgkgICAgICAgICAgICBjb3V0PDxiLWErMTw8IlxuIjsKCSAgICAgICBlbHNlIGlmKGFyclthXS5zdWZmaXgrMT09YXJyW2JdLnByZWZpeCkvL0lmIHJhbmdlIGhhcyBvbmx5IDIgYmxvY2tzLCBlZy0gezEsMSwxLDIsMiwyLDJ9CgkgICAgICAgICAgICBjb3V0PDxtYXgoYXJyW2FdLnN1ZmZpeC1hKzEsYi1hcnJbYl0ucHJlZml4KzEpPDwiXG4iOwoJICAgICAgIGVsc2UKCSAgICAgICB7CgkgICAgICAgICAgIGludCBhbnM9bWF4KGFyclthXS5zdWZmaXgtYSsxLGItYXJyW2JdLnByZWZpeCsxKTsKCSAgICAgICAgICAgLy9jb3V0PDwiQW5zIGFuZCBpbml0aWFsK2ZpbmFsIHNraXAgYXJlICI8PGFuczw8IiAiPDxhcnJbYV0uc3VmZml4KzE8PCIgIjw8YXJyW2JdLnByZWZpeC0xPDwiXG4iOwoJICAgICAgICAgICAvL2NvdXQ8PCJUaGUgMiBjaG9pY2VzIHdlcmUgIjw8YXJyW2FdLnN1ZmZpeC1hKzE8PCIgIjw8Yi1hcnJbYl0ucHJlZml4KzE8PCJcbiI7CgkgICAgICAgICAgIGFucz1tYXgoYW5zLHF1ZXJ5KDAsMCxuLTEsYXJyW2FdLnN1ZmZpeCsxLGFycltiXS5wcmVmaXgtMSx0cmVlMixhcnIpKTsKCSAgICAgICAgICAgYW5zPW1heChhbnMsMSk7CgkgICAgICAgICAgIGNvdXQ8PGFuczw8IlxuIjsKCSAgICAgICB9CgkgICAgICAgCgkgICAgfQoJfQoJcmV0dXJuIDA7Cn0K