https://www.luogu.com.cn/problem/SP1043

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 10010;
int seg[(5 * N) << 2],a[5 * N];
int qsum[(5 * N) << 2],bsum[(5 * N) << 2],qid[(5 * N) << 2],bid[(5 * N) << 2];
int n,m;
int x,y;
int sum[5 * N];
void build_tree(int l,int r,int u)
{
	if(l==r)
	{
		seg[u]=a[l];
		qsum[u]=bsum[u]=a[l];
		qid[u]=bid[u]=l;
		return;
	}
	int mid=(l+r)>>1;
	build_tree(l,mid,u*2);build_tree(mid+1,r,u*2+1);
	seg[u]=max(seg[u*2],seg[u*2+1]);
	seg[u]=max(seg[u],bsum[u*2]+qsum[u*2+1]);
	qid[u]=qid[u*2];
	if(qid[u*2]==mid && qsum[u*2]+qsum[u*2+1]>=qsum[u*2]) qid[u]=qid[u*2+1],qsum[u]=sum[qid[u]]-sum[l-1];
	bid[u]=bid[u*2+1];
	if(bid[u*2+1]==mid+1 && bsum[u*2+1]+bsum[u*2]>=bsum[u*2+1]) bid[u]=bid[u*2],bsum[u]=sum[r]-sum[bid[u]-1];
	
}
int ask(int l,int r,int u)
{
	if(l>r) return -114514;
	if(l>=x && r<=y)
	{
	 	return seg[u];
	}
	if(l==r) return -114514;
    int mid=(l+r)/2;
	if(mid>=x && mid<=y) return max(ask(l,mid,u*2)+ask(mid+1,r,u*2+1),max(ask(l,mid,u*2),ask(mid+1,r,u*2+1)));
	else if(mid>=y) return ask(l,mid,u*2);
	else return ask(mid+1,r,u*2+1);
	
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
	build_tree(1,n,1);	
	scanf("%lld",&m);
	while(m--)
	{
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",ask(1,n,1));
	}
}