关于每个值求它的beauty,至多N^2*log(N)的效率，查询一棵线段树搞定。
那么难点在于求beauty。既然要求一个不断插值的中位数，考虑用平衡树，N^2枚举每一个区间（严格说不是每一个）找中位数。普通treap很轻松。
那我介绍一种神奇的而且能用set的做法，先膜拜神犇whm。
对于每个区间的起点，值有一个，然后不断向后推，每次加二，——可以利用这个性质。
如果加的值全大于当前中位数，那么中位数++，反之，中位数-1。那么这样就弥补了iterator不能进行+=的弊端。
那么问题又来了，如何将推入的值反射回来呢？
先离散一下，给每个点的权值赋成一个小的值，并且相同的值编号大的比编号小的大，然后一个back数组反向记录，那个值对应的下标是多少，就OK了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int read()
{int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}return sum*f;
}
struct tree
{int l,r,h;
} t[2005*4];
struct node
{int id,h;
}a[2005];
int const cmp(const node a,const node b)
{return (a.h!=b.h)? (a.h<b.h):(a.id<b.id);
}
int n,h[2005],f[2005],m;
int back[2005];
int check(int x)
{set<int> st;st.insert(h[x]);set<int>::iterator it=st.begin();for(int i=x+2;i<=n;i+=2){st.insert(h[i-1]);st.insert(h[i]);if(h[i-1]>*it&&h[i]>*it)it++;elseif(h[i-1]<*it&&h[i]<*it)it--;f[back[*it]]=max(f[back[*it]],i-x+1);}
}
void build(int l,int r,int x)
{t[x].l=l;t[x].r=r;if(l==r){t[x].h=f[l];return;}int mid=(l+r)/2;build(l,mid,x*2);build(mid+1,r,x*2+1);t[x].h=max(t[x*2].h,t[x*2+1].h);
}
int q(int l,int r,int x)
{if(t[x].l>=l&&t[x].r<=r)return t[x].h;int mid=(t[x].l+t[x].r)/2,s=0;if(l<=mid)s=q(l,r,x*2);if(r>mid)s=max(s,q(l,r,x*2+1));return s;
}
int main()
{//freopen("beautiful.in","r",stdin);//freopen("beautiful.out","w",stdout);n=read();for(int i=1;i<=n;i++){a[i].id=i;a[i].h=read();f[i]=1;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++)h[a[i].id]=i,back[i]=a[i].id;for(int i=1;i<=n;i++)check(i); //for(int i=1;i<=n;i++)cout<<f[i]<<" ";//cout<<endl;build(1,n,1);m=read();int x,y,ans;for(int i=1;i<=m;i++){x=read();y=read();ans=q(x,y,1);printf("%d\n",ans);//system("pause");}
}