#include<bits/stdc++.h> using namespace std; #define int long long #define lson pos<<1 #define rson pos<<1|1 #define pii pair<int,int> #define fr first #define sc second #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w #define mk make_pair int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=300010,MAXM=1000010,inf=1000000000; int n,m,a[MAXN]; struct section{ int l,r,k,t,id; bool operator<(const section&G)const{ return l<G.l; } }q[MAXN]; struct segtree{ int t[MAXN<<2],lz[MAXN<<2]; void pushup(int pos){ t[pos]=min(t[lson],t[rson]); } void pushdown(int pos){ if(lz[pos]){ t[lson]+=lz[pos],lz[lson]+=lz[pos]; t[rson]+=lz[pos],lz[rson]+=lz[pos]; lz[pos]=0; } } void build(int pos,int l,int r,bool ty){ if(l==r){ t[pos]=ty?-a[q[l].l-1]:a[q[l].r]; return; } int mid=(l+r)>>1; build(lson,l,mid,ty); build(rson,mid+1,r,ty); pushup(pos); } void update(int pos,int l,int r,int ql,int qr,int x){ if(ql<=l&&qr>=r){ t[pos]+=x,lz[pos]+=x; return; } pushdown(pos); int mid=(l+r)>>1; if(ql<=mid)update(lson,l,mid,ql,qr,x); if(qr>mid)update(rson,mid+1,r,ql,qr,x); pushup(pos); } int query(int pos,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r)return t[pos]; pushdown(pos); int mid=(l+r)>>1; if(qr<=mid)return query(lson,l,mid,ql,qr); if(ql>mid)return query(rson,mid+1,r,ql,qr); return min(query(lson,l,mid,ql,qr),query(rson,mid+1,r,ql,qr)); } }C,D; bool cmp(section x,section y){return x.id<y.id;} void slv(){ n=read(); for(int i=1;i<=n;i++)a[i]=a[i-1]+read(); m=read(); for(int i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].k=min(read(),a[q[i].r]-a[q[i].l-1]),q[i].id=i; sort(q+1,q+m+1); for(int i=1;i<=m;i++)q[i].t=i; C.build(1,1,m,0),D.build(1,1,m,1); sort(q+1,q+m+1,cmp); for(int i=1;i<=m;i++){ int t=q[i].t,k=min(q[i].k,D.query(1,1,m,1,t)+C.query(1,1,m,t,m)); printf("%lld\n",k); C.update(1,1,m,t,m,-k); if(t!=m)D.update(1,1,m,t+1,m,k); } } signed main(){ slv(); return 0; }