记录编号	456361	评测结果	AAAAAAAAAA
题目名称	beautiful序列	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.545 s
提交时间	2017-10-04 16:51:14	内存使用	15.61 MiB

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2001;
int n,q,a[maxn],l[maxn<<1],r[maxn<<1],w[maxn],ans[maxn][maxn],cnt,i,j;
int max(int x,int y){return x>y?x:y;}
int main()
{
	freopen("abeautiful.in","r",stdin);freopen("abeautiful.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
	{
		memset(l,-1,sizeof(l));
		memset(r,-1,sizeof(r));
		l[n]=0;r[n]=0;
		cnt=0;
		for(j=i-1;j>=1;j--)
		{
			if(a[j]>a[i])cnt++; 
			if(a[j]<=a[i])cnt--;
			l[n+cnt]=i-j;
		}
		cnt=0;
		for(j=i+1;j<=n;j++)
		{
			if(a[j]>=a[i])cnt++;
			if(a[j]<a[i])cnt--;
			r[n+cnt]=j-i; 
		}
		for(j=1-i;j<=i-1;j++)
			if(l[n+j]>=0&&r[n-j]>=0)
				w[i]=max(w[i],l[n+j]+r[n - j]+1);
	}
    for(i=1;i<=n;i++)
    {
    	ans[i][i]=w[i];
    	for(j=i+1;j<=n;j++)
    		ans[i][j]=max(ans[i][j-1],w[j]);
    }
    scanf("%d",&q);
    while(q--)
    {
        int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n", ans[x][y]);
    }
	return 0;
}