// problem link : https://w...content-available-to-author-only...j.com/problems/FREQUENT/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int q,n,l,r;
int a[N];
struct node{
int ml;
int occMl;
int mr;
int occMr;
int occ;
node()
{
ml=0;
occMl=0;
mr=0;
occMr=0;
occ=0;
}
node(int l,int occl, int r,int occr, int o)
{
ml=l;
occMl=occl;
mr=r;
occMr=occr;
occ=o;
}
};
node tree[4*N];
node mergee(node &l, node &r)
{
node nd = node(l.ml,l.occMl, r.mr, r.occMr, max(l.occ, r.occ));
if (l.mr == r.ml)
nd.occ = max(nd.occ,l.occMr+r.occMl);
if (l.ml == r.ml)
nd.occMl+=r.occMl;
if (r.mr == l.mr)
nd.occMr+=l.occMr;
return nd;
}
void build(int id=0, int ns=0, int ne=n-1)
{
if (ns==ne)
{
tree[id]=node(a[ns],1,a[ns],1,1);
return ;
}
int l=2*id+1;
int r=l+1;
int mid=(ns+ne)/2;
build(l,ns,mid);
build(r,mid+1,ne);
tree[id]=mergee(tree[l],tree[r]);
}
node query(int qs, int qe, int id = 0, int ns=0, int ne=n-1)
{
if (qs>ne || qe<ns)
return node();
if (qs<=ns && ne<=qe)
return tree[id];
int l=2*id+1;
int r=l+1;
int mid = (ns+ne)/2;
node n1 = query(qs,qe,l,ns,mid);
node n2 = query(qs,qe,r,mid+1,ne);
return mergee(n1,n2);
}
int main()
{
//freopen("a.txt", "r", stdin);
cin>>n>>q;
for(int i=0 ; i<n ; i++)
cin>>a[i];
build();
while(q--)
{
cin>>l>>r;
cout<<query(--l,--r).occ<<'\n';
}
return 0;
}
Ly8gcHJvYmxlbSBsaW5rIDogaHR0cHM6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5qLmNvbS9wcm9ibGVtcy9GUkVRVUVOVC8KCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBOID0gMWU1Kzc7CmludCBxLG4sbCxyOwppbnQgYVtOXTsKCnN0cnVjdCBub2RlewogICAgaW50IG1sOwogICAgaW50IG9jY01sOwogICAgaW50IG1yOwogICAgaW50IG9jY01yOwogICAgaW50IG9jYzsKCiAgICBub2RlKCkKICAgIHsKICAgICAgICBtbD0wOwogICAgICAgIG9jY01sPTA7CiAgICAgICAgbXI9MDsKICAgICAgICBvY2NNcj0wOwogICAgICAgIG9jYz0wOwogICAgfQoKICAgIG5vZGUoaW50IGwsaW50IG9jY2wsIGludCByLGludCBvY2NyLCBpbnQgbykKICAgIHsKICAgICAgICBtbD1sOwogICAgICAgIG9jY01sPW9jY2w7CiAgICAgICAgbXI9cjsKICAgICAgICBvY2NNcj1vY2NyOwogICAgICAgIG9jYz1vOwogICAgfQp9OwoKbm9kZSB0cmVlWzQqTl07Cgpub2RlIG1lcmdlZShub2RlICZsLCBub2RlICZyKQp7CiAgICBub2RlIG5kID0gbm9kZShsLm1sLGwub2NjTWwsIHIubXIsIHIub2NjTXIsIG1heChsLm9jYywgci5vY2MpKTsKCiAgICBpZiAobC5tciA9PSByLm1sKQogICAgICAgIG5kLm9jYyA9IG1heChuZC5vY2MsbC5vY2NNcityLm9jY01sKTsKCiAgICBpZiAobC5tbCA9PSByLm1sKQogICAgICAgIG5kLm9jY01sKz1yLm9jY01sOwoKICAgIGlmIChyLm1yID09IGwubXIpCiAgICAgICAgbmQub2NjTXIrPWwub2NjTXI7CgogICAgcmV0dXJuIG5kOwp9Cgp2b2lkIGJ1aWxkKGludCBpZD0wLCBpbnQgbnM9MCwgaW50IG5lPW4tMSkKewogICAgaWYgKG5zPT1uZSkKICAgIHsKICAgICAgICB0cmVlW2lkXT1ub2RlKGFbbnNdLDEsYVtuc10sMSwxKTsKICAgICAgICByZXR1cm4gOwogICAgfQoKICAgIGludCBsPTIqaWQrMTsKICAgIGludCByPWwrMTsKICAgIGludCBtaWQ9KG5zK25lKS8yOwoKICAgIGJ1aWxkKGwsbnMsbWlkKTsKICAgIGJ1aWxkKHIsbWlkKzEsbmUpOwoKICAgIHRyZWVbaWRdPW1lcmdlZSh0cmVlW2xdLHRyZWVbcl0pOwp9Cgpub2RlIHF1ZXJ5KGludCBxcywgaW50IHFlLCBpbnQgaWQgPSAwLCBpbnQgbnM9MCwgaW50IG5lPW4tMSkKewogICAgaWYgKHFzPm5lIHx8IHFlPG5zKQogICAgICAgIHJldHVybiBub2RlKCk7CgogICAgaWYgKHFzPD1ucyAmJiBuZTw9cWUpCiAgICAgICAgcmV0dXJuIHRyZWVbaWRdOwoKICAgIGludCBsPTIqaWQrMTsKICAgIGludCByPWwrMTsKICAgIGludCBtaWQgPSAobnMrbmUpLzI7CgogICAgbm9kZSBuMSA9IHF1ZXJ5KHFzLHFlLGwsbnMsbWlkKTsKICAgIG5vZGUgbjIgPSBxdWVyeShxcyxxZSxyLG1pZCsxLG5lKTsKCiAgICByZXR1cm4gbWVyZ2VlKG4xLG4yKTsKCn0KCgppbnQgbWFpbigpCnsKICAgIC8vZnJlb3BlbigiYS50eHQiLCAiciIsIHN0ZGluKTsKICAgIGNpbj4+bj4+cTsKCiAgICBmb3IoaW50IGk9MCA7IGk8biA7IGkrKykKICAgICAgICBjaW4+PmFbaV07CgogICAgYnVpbGQoKTsKICAgIHdoaWxlKHEtLSkKICAgIHsKICAgICAgICBjaW4+Pmw+PnI7CiAgICAgICAgY291dDw8cXVlcnkoLS1sLC0tcikub2NjPDwnXG4nOwogICAgfQoKICAgIHJldHVybiAwOwoKfQo=