#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
struct node
{
std::pair<int,int> pref={0, 0}, suff={0,0}, all={0, 0};
int len=0;
void combine(const node &left, const node &right)
{
len=left.len+right.len;
pref=left.pref;
suff=right.suff;
all=std::max(left.all, right.all);
if(left.suff.second==right.pref.second)
{
all=std::max(all, std::pair<int,int>(left.suff.first+right.pref.first, left.suff.second));
if(left.pref.first==left.len)
{
pref=std::max(pref, std::pair<int,int>(left.len+right.pref.first, left.suff.second));
}
if(right.suff.first==right.len)
{
suff=std::max(suff, std::pair<int,int>(right.len+left.suff.first, left.suff.second));
}
}
}
};
std::vector<node> tree;
std::vector<int> arr;
void build(int l, int r, int i=1)
{
if(l==r)
{
tree[i].all=std::pair<int,int>(1, arr[l]);
tree[i].pref=std::pair<int,int>(1, arr[l]);
tree[i].suff=std::pair<int,int>(1, arr[l]);
tree[i].len=1;
return;
}
int m=(l+r)>>1;
int j=i<<1;
int k=j|1;
build(l, m, j);
build(m+1, r, k);
tree[i].combine(tree[j], tree[k]);
}
node query(int l, int r, int tl , int tr, int i=1)
{
if(l==tl && r==tr)
{
return tree[i];
}
int tm=(tl+tr)>>1;
int j=i<<1;
int k=j|1;
if(r<=tm)
{
return query(l, r, tl, tm, j);
}
if(l>=tm+1)
{
return query(l, r, tm+1, tr, k);
}
node left=query(l, tm, tl, tm, j);
node right=query(tm+1, r, tm+1, tr, k);
node res;
res.combine(left, right);
return res;
}
int main() {
while(1)
{
int n=0;
scanf("%d", &n);
if(n<1)
{
break;
}
int q=0;
scanf("%d", &q);
arr.resize(n);
tree.resize(4*n);
for(auto &it: arr)
{
scanf("%d", &it);
}
build(0, n-1);
for(int i=0; i<q; ++i)
{
int l,r;
scanf("%d %d", &l, &r);
node res;
res=query(l-1, r-1, 0, n-1);
printf("%d\n", res.all.first);
}
}
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxhbGdvcml0aG0+CnN0cnVjdCBub2RlCnsKCXN0ZDo6cGFpcjxpbnQsaW50PiBwcmVmPXswLCAwfSwgc3VmZj17MCwwfSwgYWxsPXswLCAwfTsKCWludCBsZW49MDsKCXZvaWQgY29tYmluZShjb25zdCBub2RlICZsZWZ0LCBjb25zdCBub2RlICZyaWdodCkKCXsKICAgICAgICAgbGVuPWxlZnQubGVuK3JpZ2h0LmxlbjsKICAgICAgICAgcHJlZj1sZWZ0LnByZWY7CiAgICAgICAgIHN1ZmY9cmlnaHQuc3VmZjsKICAgICAgICAgYWxsPXN0ZDo6bWF4KGxlZnQuYWxsLCByaWdodC5hbGwpOwogICAgICAgICBpZihsZWZ0LnN1ZmYuc2Vjb25kPT1yaWdodC5wcmVmLnNlY29uZCkKICAgICAgICAgewogICAgICAgICAgICAgYWxsPXN0ZDo6bWF4KGFsbCwgc3RkOjpwYWlyPGludCxpbnQ+KGxlZnQuc3VmZi5maXJzdCtyaWdodC5wcmVmLmZpcnN0LCBsZWZ0LnN1ZmYuc2Vjb25kKSk7CiAgICAgICAgICAgICBpZihsZWZ0LnByZWYuZmlyc3Q9PWxlZnQubGVuKQogICAgICAgICAgICAgewogICAgICAgICAgICAgICAgIHByZWY9c3RkOjptYXgocHJlZiwgc3RkOjpwYWlyPGludCxpbnQ+KGxlZnQubGVuK3JpZ2h0LnByZWYuZmlyc3QsIGxlZnQuc3VmZi5zZWNvbmQpKTsKICAgICAgICAgICAgIH0KICAgICAgICAgICAgIGlmKHJpZ2h0LnN1ZmYuZmlyc3Q9PXJpZ2h0LmxlbikKICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICBzdWZmPXN0ZDo6bWF4KHN1ZmYsIHN0ZDo6cGFpcjxpbnQsaW50PihyaWdodC5sZW4rbGVmdC5zdWZmLmZpcnN0LCBsZWZ0LnN1ZmYuc2Vjb25kKSk7CiAgICAgICAgICAgICB9CiAgICAgICAgIH0KCX0KfTsKc3RkOjp2ZWN0b3I8bm9kZT4gdHJlZTsKc3RkOjp2ZWN0b3I8aW50PiBhcnI7CnZvaWQgYnVpbGQoaW50IGwsIGludCByLCBpbnQgaT0xKQp7CiAgICBpZihsPT1yKQogICAgewogICAgICAgIHRyZWVbaV0uYWxsPXN0ZDo6cGFpcjxpbnQsaW50PigxLCBhcnJbbF0pOwogICAgICAgIHRyZWVbaV0ucHJlZj1zdGQ6OnBhaXI8aW50LGludD4oMSwgYXJyW2xdKTsKICAgICAgICB0cmVlW2ldLnN1ZmY9c3RkOjpwYWlyPGludCxpbnQ+KDEsIGFycltsXSk7CiAgICAgICAgdHJlZVtpXS5sZW49MTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgbT0obCtyKT4+MTsKICAgIGludCBqPWk8PDE7CiAgICBpbnQgaz1qfDE7CiAgICBidWlsZChsLCBtLCBqKTsKICAgIGJ1aWxkKG0rMSwgciwgayk7CiAgICB0cmVlW2ldLmNvbWJpbmUodHJlZVtqXSwgdHJlZVtrXSk7Cn0Kbm9kZSBxdWVyeShpbnQgbCwgaW50IHIsIGludCB0bCAsIGludCB0ciwgaW50IGk9MSkKewogICAgaWYobD09dGwgJiYgcj09dHIpCiAgICB7CiAgICAgICAgcmV0dXJuIHRyZWVbaV07CiAgICB9CiAgICBpbnQgdG09KHRsK3RyKT4+MTsKICAgIGludCBqPWk8PDE7CiAgICBpbnQgaz1qfDE7CiAgICBpZihyPD10bSkKICAgIHsKICAgICAgICByZXR1cm4gcXVlcnkobCwgciwgdGwsIHRtLCBqKTsKICAgIH0KICAgIGlmKGw+PXRtKzEpCiAgICB7CiAgICAgICAgcmV0dXJuIHF1ZXJ5KGwsIHIsIHRtKzEsIHRyLCBrKTsKICAgIH0KICAgIG5vZGUgbGVmdD1xdWVyeShsLCB0bSwgdGwsIHRtLCBqKTsKICAgIG5vZGUgcmlnaHQ9cXVlcnkodG0rMSwgciwgdG0rMSwgdHIsIGspOwogICAgbm9kZSByZXM7CiAgICByZXMuY29tYmluZShsZWZ0LCByaWdodCk7CiAgICByZXR1cm4gcmVzOwp9CmludCBtYWluKCkgewoJd2hpbGUoMSkKCXsKCQlpbnQgbj0wOwoJCXNjYW5mKCIlZCIsICZuKTsKCQlpZihuPDEpCgkJewoJCQlicmVhazsKCQl9CgkJaW50IHE9MDsKCQlzY2FuZigiJWQiLCAmcSk7CgkJYXJyLnJlc2l6ZShuKTsKCQl0cmVlLnJlc2l6ZSg0Km4pOwoJCWZvcihhdXRvICZpdDogYXJyKQoJCXsKCQkJc2NhbmYoIiVkIiwgJml0KTsKCQl9CgkJYnVpbGQoMCwgbi0xKTsKCQlmb3IoaW50IGk9MDsgaTxxOyArK2kpCgkJewoJCQlpbnQgbCxyOwoJCQlzY2FuZigiJWQgJWQiLCAmbCwgJnIpOwoJCQlub2RlIHJlczsKICAgICAgICAgICAgcmVzPXF1ZXJ5KGwtMSwgci0xLCAwLCBuLTEpOwoJCQlwcmludGYoIiVkXG4iLCByZXMuYWxsLmZpcnN0KTsKCQl9Cgl9CglyZXR1cm4gMDsKfQo=