[ index tree ]

#include<stdio.h>
#define MAX 100002
#define fmax(A,B) ((A)>(B)) ? (A) : (B)
int ifm[MAX];
int Dy1[MAX],Dy2[MAX];
int tree[3*MAX],temp=1;
int n,maxm,answer;
void input()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++) {
		scanf("%d",&ifm[i]);
	}
}
void setting()
{
	int i,V;
	for(;;) {
		if(temp>=n) break;
		temp*=2;
	}
	for(i=1;i<=3*n;i++) tree[i]=-99999999;
	for(i=1;i<=n;i++) {
		V=i+temp-1;
		tree[V]=Dy2[i];
		while(V>1) {
			if(V%2==0) V=V/2;
			else V=(V-1)/2;
			tree[V]=fmax(tree[V],Dy2[i]);
		}
	}
}
void search_tree(int l,int r)
{
	maxm=-99999999;
	while(l<=r) {
		if(l==r) {
			maxm=fmax(maxm,tree[l]);
			break;
		}
		if(l%2==1) {
			maxm=fmax(maxm,tree[l]);
			l=(l+1)/2;
		}
		else {
			l/=2;
		}
		if(r%2==0) {
			maxm=fmax(maxm,tree[r]);
			r=(r-1)/2;
		}
		else {
			r/=2;
		}
	}
}
void Dynamic()
{
	answer=-99999999;
	int i;
	for(i=1;i<=n;i++) Dy1[i]=0; Dy2[i]=0;
	for(i=1;i<=n;i++) {
		if(ifm[i]<Dy1[i-1]+ifm[i]) Dy1[i]=Dy1[i-1]+ifm[i];
		else Dy1[i]=ifm[i];
	}
	for(i=n;i>=1;i--) {
		if(ifm[i]<Dy2[i+1]+ifm[i]) Dy2[i]=Dy2[i+1]+ifm[i];
		else Dy2[i]=ifm[i];
	}
	setting();
	for(i=1;i<=n;i++) {
		search_tree(i+temp,n+temp-1);
		if(answer<maxm+Dy1[i]) answer=maxm+Dy1[i];
	}
}
void output()
{
	printf("%d\n",answer);
}
int main()
{
	for(;;) {
		input();
		if(n==0) break;
		Dynamic();
		output();
	}
	return 0;
}