当时脑抽，写了一个错误的 $O(m\sqrt n)$ 做法，然后发现除了#10，全WA了，然后改成了带优化的暴力，发现#10TLE了，然后一顿乱搞AC了

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename P>inline void read(P&x){bool f=0;x=0;char c=getchar();while(!isdigit(c)) f|=c=='-',c=getchar();while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();x=f?~(x-1):x;}
template<typename P>inline void write(P x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar((x%10)^48);}
const int N=1e5+5,M=318;
int n,m,op,x,y,k,a[N],cnt[M],Max[M],id[N],L[M],R[M],Sqrt,len,add[M],res;
inline void down(int x){
	for(register int i=L[x];i<=R[x];i++) a[i]+=add[x];
	add[x]=cnt[x]=0,Max[x]=-1e17;
	for(register int i=L[x];i<=R[x];i++)
		cnt[x]+=a[i],Max[x]=max(Max[x],cnt[x]);
}inline void Build(){
	Sqrt=sqrt(n),len=n/Sqrt;
	for(register int i=1;i<=len;i++) L[i]=R[i-1]+1,R[i]=i*Sqrt;
	if(R[len]^n) len++,L[len]=R[len-1]+1,R[len]=n;
	for(register int i=1,ID=1;i<=n;i++) id[i]=ID,ID+=i==R[ID];
	for(register int i=1;i<=len;i++) down(i);
}inline void change(int l,int r,int k){
	if(id[l]==id[r]){
		for(register int i=l;i<=r;i++) a[i]+=k;
		down(id[l]);return;
	}for(register int i=l;i<=R[id[l]];i++) a[i]+=k;
	for(register int i=L[id[r]];i<=r;i++) a[i]+=k;
	down(id[l]),down(id[r]);
	for(register int i=id[l]+1;i<id[r];i++){
		res++;
		if(res<=1e7) add[i]+=k,down(i);
		else add[i]+=k,Max[i]+=k,cnt[i]+=(R[i]-L[i]+1)*k;
	}
}inline int Query(int l,int r){
	register int ans=-1e17,sum=0;
	if(id[l]==id[r]){
		down(id[l]);
		for(register int i=1;i<id[l];i++) sum+=cnt[i];
		for(register int i=L[id[l]];i<=r;i++){
			sum+=a[i];
			if(l<=i) ans=max(ans,sum);
		}return ans;
	}down(id[l]),down(id[r]);
	for(register int i=1;i<id[l];i++) sum+=cnt[i];
	for(register int i=L[id[l]];i<=R[id[l]];i++){
		sum+=a[i];
		if(l<=i) ans=max(ans,sum);
	}for(register int i=id[l]+1;i<id[r];i++)
		ans=max(ans,sum+Max[i]),sum+=cnt[i];
	for(register int i=L[id[r]];i<=r;i++)
		sum+=a[i],ans=max(ans,sum);
	return ans;
}
signed main(){
	read(n);
	for(register int i=1;i<=n;i++) read(a[i]);
	Build();read(m);
	while(m--){
		read(op),read(x),read(y);
		if(!op) read(k),change(x,y,k);
		else write(Query(x,y)),putchar('\n');
	}
	return 0;
}