20行的归并+10行的线段树（现在线段树真是越写越短了）+10行主程序（连主程序都缩过行） = =丧心病狂
struct里连开10个，用大括号直接初始化真是爽翻了
#include <cstdio>
#define mid ((l+r)>>1)
struct node
{
int ls,lj,rs,rj,s,ss,j,js,l,r;
} tr[],ans;
int a[];
int n,m,p,q;
inline int max(int p,int q){return(p>q)?p:q;}
node merge(node p,node q)
{
node ans;
ans.l=p.l;ans.r=q.r;
ans.ls=p.ls;ans.lj=p.lj;
ans.rs=q.rs;ans.rj=q.rj; if(p.s>q.s) ans.s=p.s,ans.ss=p.ss;
else ans.s=q.s,ans.ss=q.ss;
if(a[p.r]<=a[q.l])
if(ans.s<p.rs+q.ls)
ans.s=p.rs+q.ls,ans.ss=p.r-p.rs+;
if(ans.ss==p.l) ans.ls=ans.s;
if(ans.ss+ans.s-==q.r) ans.rs=ans.s; if(p.j>q.j) ans.j=p.j,ans.js=p.js;
else ans.j=q.j,ans.js=q.js;
if(a[p.r]>=a[q.l])
if(ans.j<p.rj+q.lj)
ans.j=p.rj+q.lj,ans.js=p.r-p.rj+;
if(ans.js==p.l) ans.lj=ans.j;
if(ans.js+ans.j-==q.r) ans.rj=ans.j;
return ans;
}
void build(int now,int l,int r)
{
if(l!=r)
build(now<<,l,mid),build(now<<|,mid+,r),tr[now]=merge(tr[now<<],tr[now<<|]);
else
tr[now]={,,,,,l,,l,l,l};
}
node que(int now,int l,int r,int p,int q)
{
if(l==p && r==q) return tr[now];
if(q<=mid) return que(now<<,l,mid,p,q);
else if(p>mid) return que(now<<|,mid+,r,p,q);
else return merge(que(now<<,l,mid,p,mid),que(now<<|,mid+,r,mid+,q));
}
int main()
{
for(scanf("%d",&n),p=;p<=n;p++)
scanf("%d",&a[p]);
build(,,n);
for(scanf("%d",&m);m;m--)
scanf("%d%d",&p,&q),ans=que(,,n,p,q),printf("%d\n",max(ans.s,ans.j));
return ;
}
事实上应该是1A的，但是输出的时候没回车（mdzz）错了一发