//frequent values of spoj with dedication..:P
#include<cstdio>
#include<iostream>
#include<string.h>
#include<math.h>
#define M 100005
struct node
{
int lf,rf,mf;
}
tree[50*M],tree1[50*M];
int arr[M];
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int max2(int a,int b,int c)
{
if(a>=b&&a>=c)
return a;
else if(b>=a&&b>=c)
return b;
else
return c;
}
int getmid(int a,int b)
{
return ((a+b)/2);
}
void buildtree(int node,int a,int b)
{
if(a>b)return;
if(a==b)
{tree[node].lf=tree[node].rf=tree[node].mf=1;return;}
int mid=getmid(a,b);
buildtree(2*node,a,mid);
buildtree(2*node+1,mid+1,b);
if(arr[a]==arr[mid+1])
tree[node].lf=tree[2*node].lf+tree[2*node+1].lf;
else
tree[node].lf=tree[2*node].lf;
if(arr[mid]==arr[b])
tree[node].rf=tree[2*node].rf+tree[2*node+1].rf;
else
tree[node].rf=tree[2*node+1].rf;
if(arr[mid]==arr[mid+1])
tree[node].mf=max2(tree[2*node].mf,tree[2*node+1].mf,tree[2*node].rf+tree[2*node+1].lf);
else
tree[node].mf=max(tree[2*node].mf,tree[2*node+1].mf);
return ;
}
int query(int node,int a,int b,int i,int j)
{
// printf("node %d %d %d\n",a,b,node);
if(a>b||b<i||a>j){return -100009;}
if(a>=i&&b<=j)
{
// printf("the leaf node %d\n",node);
tree1[node].lf=tree[node].lf;
tree1[node].rf=tree[node].rf;
tree1[node].mf=tree[node].mf;
return node;
}
int p,q,res;
int mid=getmid(a,b);
p=query(2*node,a,mid,i,j);
q=query(2*node+1,mid+1,b,i,j);
if(p==-100009&&q==-100009)return -100009;
else if(p==-100009)
{tree1[node].lf=tree1[q].lf;tree1[node].mf=tree1[q].mf;tree1[node].rf=tree1[q].rf;
//printf("sonu %d %d %d %d\n",p,q,node,tree1[node].mf);
return node;}
else if(q==-100009)
{tree1[node].lf=tree1[p].lf;tree1[node].mf=tree1[p].mf;tree1[node].rf=tree1[p].rf;
//printf("mk %d %d %d %d %d\n",p,q,tree1[p].mf,node,tree1[node].mf);
return node;}
else
{
if(arr[mid]==arr[mid+1])
tree1[node].mf=max2(tree1[p].mf,tree1[q].mf,tree1[p].rf+tree1[q].lf);
else
tree1[node].mf=max(tree1[p].mf,tree1[q].mf);
if(arr[a]==arr[mid+1])
tree1[node].lf=tree1[p].lf+tree[q].lf;
else
tree[node].lf=tree1[p].lf;
if(arr[mid]==arr[b])
tree1[node].rf=tree1[p].rf+tree1[q].rf;
else
tree1[node].rf=tree1[q].rf;
// printf("mama %d %d\n",node,tree1[node].mf);
return node;
}
}
int main()
{
int t,a,b,c,i,j,k,l,q,n;
while(1)
{
if(n==0)break;
for(i=1;i<=n;i++)
buildtree(1,1,n);
// for(i=1;i<=25;i++)printf("%d %d %d %d\n",i,tree[i].lf,tree[i].rf,tree[i].mf);
//system("pause");
//buildtree is fine :P
while(q--)
{
printf("%d\n",tree1
[query
(1,1,n
,a
,b
)].
mf); }
}
// system("pause");
}
Ly9mcmVxdWVudCB2YWx1ZXMgb2Ygc3BvaiB3aXRoIGRlZGljYXRpb24uLjpQCgojaW5jbHVkZTxjc3RkaW8+CiNpbmNsdWRlPGlvc3RyZWFtPgojaW5jbHVkZTxzdHJpbmcuaD4KI2luY2x1ZGU8bWF0aC5oPgojZGVmaW5lIE0gMTAwMDA1CgoKCnN0cnVjdCBub2RlCnsKCWludCAgbGYscmYsbWY7Cn0KdHJlZVs1MCpNXSx0cmVlMVs1MCpNXTsKCgppbnQgYXJyW01dOwoKaW50IG1heChpbnQgYSxpbnQgYikKewoJaWYoYT5iKQoJcmV0dXJuIGE7CgllbHNlCglyZXR1cm4gYjsKfQoKaW50IG1heDIoaW50IGEsaW50IGIsaW50IGMpCnsKCWlmKGE+PWImJmE+PWMpCglyZXR1cm4gYTsKCWVsc2UgaWYoYj49YSYmYj49YykKCXJldHVybiBiOwoJZWxzZQoJcmV0dXJuIGM7Cn0KCgppbnQgZ2V0bWlkKGludCBhLGludCBiKQp7CglyZXR1cm4gKChhK2IpLzIpOwp9Cgp2b2lkICBidWlsZHRyZWUoaW50IG5vZGUsaW50IGEsaW50IGIpCnsKCWlmKGE+YilyZXR1cm47CglpZihhPT1iKQogCXt0cmVlW25vZGVdLmxmPXRyZWVbbm9kZV0ucmY9dHJlZVtub2RlXS5tZj0xO3JldHVybjt9CgkKCWludCBtaWQ9Z2V0bWlkKGEsYik7CglidWlsZHRyZWUoMipub2RlLGEsbWlkKTsKCWJ1aWxkdHJlZSgyKm5vZGUrMSxtaWQrMSxiKTsKCWlmKGFyclthXT09YXJyW21pZCsxXSkKCXRyZWVbbm9kZV0ubGY9dHJlZVsyKm5vZGVdLmxmK3RyZWVbMipub2RlKzFdLmxmOwoJZWxzZQoJdHJlZVtub2RlXS5sZj10cmVlWzIqbm9kZV0ubGY7CglpZihhcnJbbWlkXT09YXJyW2JdKQoJdHJlZVtub2RlXS5yZj10cmVlWzIqbm9kZV0ucmYrdHJlZVsyKm5vZGUrMV0ucmY7CgllbHNlCgl0cmVlW25vZGVdLnJmPXRyZWVbMipub2RlKzFdLnJmOwoJCglpZihhcnJbbWlkXT09YXJyW21pZCsxXSkKCXRyZWVbbm9kZV0ubWY9bWF4Mih0cmVlWzIqbm9kZV0ubWYsdHJlZVsyKm5vZGUrMV0ubWYsdHJlZVsyKm5vZGVdLnJmK3RyZWVbMipub2RlKzFdLmxmKTsKCWVsc2UKCXRyZWVbbm9kZV0ubWY9bWF4KHRyZWVbMipub2RlXS5tZix0cmVlWzIqbm9kZSsxXS5tZik7CglyZXR1cm4gOwp9CgoKCgppbnQgcXVlcnkoaW50IG5vZGUsaW50IGEsaW50IGIsaW50IGksaW50IGopCnsKLy8JcHJpbnRmKCJub2RlICAlZCAgICVkICAgJWRcbiIsYSxiLG5vZGUpOwoJaWYoYT5ifHxiPGl8fGE+ail7cmV0dXJuIC0xMDAwMDk7fQoJaWYoYT49aSYmYjw9aikKCXsKCS8vCXByaW50ZigidGhlIGxlYWYgbm9kZSAgICVkXG4iLG5vZGUpOwogICAgdHJlZTFbbm9kZV0ubGY9dHJlZVtub2RlXS5sZjsKICAgIHRyZWUxW25vZGVdLnJmPXRyZWVbbm9kZV0ucmY7CiAgICB0cmVlMVtub2RlXS5tZj10cmVlW25vZGVdLm1mOwoKCXJldHVybiBub2RlOwoJfQoJaW50IHAscSxyZXM7CglpbnQgbWlkPWdldG1pZChhLGIpOwoJCglwPXF1ZXJ5KDIqbm9kZSxhLG1pZCxpLGopOwoJcT1xdWVyeSgyKm5vZGUrMSxtaWQrMSxiLGksaik7CgoJaWYocD09LTEwMDAwOSYmcT09LTEwMDAwOSlyZXR1cm4gLTEwMDAwOTsKCWVsc2UgaWYocD09LTEwMDAwOSkKCXt0cmVlMVtub2RlXS5sZj10cmVlMVtxXS5sZjt0cmVlMVtub2RlXS5tZj10cmVlMVtxXS5tZjt0cmVlMVtub2RlXS5yZj10cmVlMVtxXS5yZjsKCS8vcHJpbnRmKCJzb251ICAlZCAgICVkICAgICAlZCAgJWRcbiIscCxxLG5vZGUsdHJlZTFbbm9kZV0ubWYpOwoJcmV0dXJuIG5vZGU7fQoJZWxzZSBpZihxPT0tMTAwMDA5KQogICAge3RyZWUxW25vZGVdLmxmPXRyZWUxW3BdLmxmO3RyZWUxW25vZGVdLm1mPXRyZWUxW3BdLm1mO3RyZWUxW25vZGVdLnJmPXRyZWUxW3BdLnJmOwoJLy9wcmludGYoIm1rICAlZCAgICAlZCAgJWQgICAlZCAgICVkXG4iLHAscSx0cmVlMVtwXS5tZixub2RlLHRyZWUxW25vZGVdLm1mKTsKCXJldHVybiBub2RlO30KCWVsc2UKCXsKCQlpZihhcnJbbWlkXT09YXJyW21pZCsxXSkKCQl0cmVlMVtub2RlXS5tZj1tYXgyKHRyZWUxW3BdLm1mLHRyZWUxW3FdLm1mLHRyZWUxW3BdLnJmK3RyZWUxW3FdLmxmKTsKCQllbHNlCgkJdHJlZTFbbm9kZV0ubWY9bWF4KHRyZWUxW3BdLm1mLHRyZWUxW3FdLm1mKTsKICAgICAgICBpZihhcnJbYV09PWFyclttaWQrMV0pCgkgICAgdHJlZTFbbm9kZV0ubGY9dHJlZTFbcF0ubGYrdHJlZVtxXS5sZjsKCSAgICBlbHNlCgkgICAgdHJlZVtub2RlXS5sZj10cmVlMVtwXS5sZjsKCSAgICBpZihhcnJbbWlkXT09YXJyW2JdKQoJICAgIHRyZWUxW25vZGVdLnJmPXRyZWUxW3BdLnJmK3RyZWUxW3FdLnJmOwoJICAgIGVsc2UKCSAgICB0cmVlMVtub2RlXS5yZj10cmVlMVtxXS5yZjsKCQkKCgkvLwlwcmludGYoIm1hbWEgICVkICAlZFxuIixub2RlLHRyZWUxW25vZGVdLm1mKTsKCQlyZXR1cm4gbm9kZTsKCX0KCn0KCQoKCmludCBtYWluKCkKewoJaW50IHQsYSxiLGMsaSxqLGssbCxxLG47CgoJd2hpbGUoMSkKCXsKCXNjYW5mKCIlZCIsJm4pOwoJaWYobj09MClicmVhazsKCXNjYW5mKCIlZCIsJnEpOwoJZm9yKGk9MTtpPD1uO2krKykKCXNjYW5mKCIlZCIsJmFycltpXSk7CgoJbWVtc2V0KHRyZWUsMCxzaXplb2YodHJlZSkpOwoJbWVtc2V0KHRyZWUxLDAsc2l6ZW9mKHRyZWUpKTsKCgkgYnVpbGR0cmVlKDEsMSxuKTsKCS8vIGZvcihpPTE7aTw9MjU7aSsrKXByaW50ZigiJWQgICAlZCAgICAlZCAgICAlZFxuIixpLHRyZWVbaV0ubGYsdHJlZVtpXS5yZix0cmVlW2ldLm1mKTsKIC8vc3lzdGVtKCJwYXVzZSIpOwovL2J1aWxkdHJlZSBpcyBmaW5lIDpQCiAgICAgd2hpbGUocS0tKQogICAgIHsKCQkJc2NhbmYoIiVkJWQiLCZhLCZiKTsKCgkJCXByaW50ZigiJWRcbiIsdHJlZTFbcXVlcnkoMSwxLG4sYSxiKV0ubWYpOwoJfQogIH0KLy8Jc3lzdGVtKCJwYXVzZSIpOwp9Cg==