写猫树大小要开到 $2$ 的次幂，如果真的开不下，这里给出一些实现的细节。

我RE了好多发QwQ

1. $l>n$ 直接退出。
2. $mid>n$ 不进行本区间的计算（还是要递归子区间）
3. $r>n$ 使 $r=n$。

#include<bits/stdc++.h>
using namespace std;
template<typename T=int>
T Read(){
	char c;bool f=1;
	while(c=getchar(),c<'0'||c>'9') if(c=='-') f=0;
	T x=c^'0';
	while(c=getchar(),c>='0'&&c<='9') x=x*10+(c^'0');
	return f?x:-x;
}
const int N=5e4,L=16;
int n,nl,a[N+5];
int f[L][N+5],g[L][N+5],SIZE=N+5;
void Build(int l,int r,int f[]=::f[0],int g[]=::g[0]){
	if(l>n||l==r) return;//
	int mid=(l+r)>>1,fs,gs;
	Build(l,mid,f+SIZE,g+SIZE),Build(mid+1,r,f+SIZE,g+SIZE);
	if(mid>n) return;//
	g[mid]=f[mid]=fs=gs=a[mid];
	for(int i=mid-1;i>=l;--i) f[i]=max(f[i+1],fs=max(fs,0)+a[i]),g[i]=max(g[i+1],gs+=a[i]);
	g[mid+1]=f[mid+1]=fs=gs=a[mid+1];
	r=min(r,n);//
	for(int i=mid+2;i<=r;++i) f[i]=max(f[i-1],fs=max(fs,0)+a[i]),g[i]=max(g[i-1],gs+=a[i]);
}

int main(){
	n=Read();
	for(int i=1;i<=n;++i) a[i]=Read();
	Build(1,nl=(1<<(__lg(n-1)+1)));
	int q=Read();
	while(q--){
#define p(x) (nl-1+x)
		int l=Read(),r=Read(),d=__lg(p(l))-__lg(p(l)^p(r))-1;
		if(l==r) printf("%d\n",a[l]);
		else printf("%d\n",max(max(f[d][l],f[d][r]),g[d][l]+g[d][r]));
	}
}