#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define p1(x) x.first #define p2(x) x.second #define endl "\n" int n,Q; int a[300400],s[300400]; int l[300400],r[300400],k[300400]; int w[300400],rk[300400]; int p[300400],q[300400]; inline bool cmp(int x,int y){ return l[x]<l[y]; } int A[300400<<2],B[300400<<2],C[300400<<2]; int tga[300400<<2],tgb[300400<<2]; #define lc(x) (x<<1) #define rc(x) (x<<1|1) inline void upd(int x){ A[x]=max(A[lc(x)],A[rc(x)]); B[x]=min(B[lc(x)],B[rc(x)]); C[x]=min({C[lc(x)],C[rc(x)],B[lc(x)]-A[rc(x)]}); } inline void pd(int x){ if(tga[x]){ A[lc(x)]+=tga[x]; A[rc(x)]+=tga[x]; tga[lc(x)]+=tga[x]; tga[rc(x)]+=tga[x]; C[lc(x)]-=tga[x]; C[rc(x)]-=tga[x]; tga[x]=0; } if(tgb[x]){ B[lc(x)]+=tgb[x]; B[rc(x)]+=tgb[x]; tgb[lc(x)]+=tgb[x]; tgb[rc(x)]+=tgb[x]; C[lc(x)]+=tgb[x]; C[rc(x)]+=tgb[x]; tgb[x]=0; } upd(x); } inline void bd(int x,int l,int r){ if(l==r){ A[x]=-p[l]; B[x]=-q[l]; C[x]=B[x]-A[x]; // cout<<l<<" "<<A[x]<<" "<<B[x]<<endl; return ; } int mid=l+r>>1; bd(lc(x),l,mid); bd(rc(x),mid+1,r); upd(x); } inline void modA(int x,int l,int r,int L,int R,int c){ if(L>R)return ; if(L<=l&&r<=R){ A[x]+=c; C[x]-=c; tga[x]+=c; return ; } pd(x); int mid=l+r>>1; if(L<=mid)modA(lc(x),l,mid,L,R,c); if(R>mid)modA(rc(x),mid+1,r,L,R,c); upd(x); } inline void modB(int x,int l,int r,int L,int R,int c){ if(L>R)return ; if(L<=l&&r<=R){ B[x]+=c; C[x]+=c; tgb[x]+=c; return ; } pd(x); int mid=l+r>>1; if(L<=mid)modB(lc(x),l,mid,L,R,c); if(R>mid)modB(rc(x),mid+1,r,L,R,c); upd(x); } inline int gA(int x,int l,int r,int L,int R){ if(L<=l&&r<=R)return A[x]; pd(x); int mid=l+r>>1; if(R<=mid)return gA(lc(x),l,mid,L,R); if(L>mid)return gA(rc(x),mid+1,r,L,R); return max(gA(lc(x),l,mid,L,R),gA(rc(x),mid+1,r,L,R)); } inline int gB(int x,int l,int r,int L,int R){ if(L<=l&&r<=R)return B[x]; pd(x); int mid=l+r>>1; if(R<=mid)return gB(lc(x),l,mid,L,R); if(L>mid)return gB(rc(x),mid+1,r,L,R); return min(gB(lc(x),l,mid,L,R),gB(rc(x),mid+1,r,L,R)); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("genshin.in","r",stdin); // freopen("genshin.out","w",stdout); // system("grep VmPeak /proc/$PPID/status"); cin>>n; for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i]; cin>>Q; for(int i=1;i<=Q;i++) cin>>l[i]>>r[i]>>k[i],w[i]=i; sort(w+1,w+Q+1,cmp); for(int i=1;i<=Q;i++) rk[w[i]]=i; for(int i=1;i<=n;i++) p[i]=s[r[w[i]]],q[i]=s[l[w[i]]-1]; bd(1,1,Q); for(int i=1;i<=Q;i++){ int x=min(k[i],gB(1,1,Q,1,rk[i])-gA(1,1,Q,rk[i],Q)); // cout<<gB(1,1,Q,1,rk[i])<<" "<<gA(1,1,Q,rk[i],Q)<<endl; modA(1,1,Q,rk[i],Q,x); modB(1,1,Q,rk[i]+1,Q,x); cout<<x<<endl; } cout.flush(); return 0; }