#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair using namespace std; typedef long long ll; const int maxn=3e5+10; const ll inf=1e17; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,m,a[maxn],p[maxn]; int pos[maxn]; struct Range { int l,r,fl; }R[maxn]; bool operator<(Range a,Range b){ if(a.l<b.l)return a.l<b.l; if(a.r<b.r)return a.r<b.r; return a.fl<b.fl; } ll s[maxn]; struct node { int l,r,k,fl; }d[maxn]; struct nd { ll mx;//max l[i]-s[i-1] ll mn;//min r[i]+1-s[i] ll res; }; nd operator+(nd a,nd b){ nd res; res.mx=max(a.mx,b.mx); res.mn=min(a.mn,b.mn); res.res=min(min(a.res,b.res),b.mn-a.mx); return res; } struct SegTree { struct node { nd x;ll tg1,tg2; }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define x(p) d[p].x #define tg1(p) d[p].tg1 #define tg2(p) d[p].tg2 void cl(int p,ll a,ll b){ x(p).mn+=a,x(p).mx+=b,x(p).res+=a-b; tg1(p)+=a,tg2(p)+=b; }void pd(int p){ cl(ls(p),tg1(p),tg2(p));cl(rs(p),tg1(p),tg2(p));tg1(p)=tg2(p)=0; }void pu(int p){ x(p)=x(ls(p))+x(rs(p)); } void bd(int l,int r,int p){ if(l==r){ x(p).mn=inf,x(p).mx=-inf,x(p).res=2*inf; return; }int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); }void modify(int l,int r,int s,int t,int p,int a,int b){ if(l>r)return; if(l<=s&&t<=r){ cl(p,a,b);return; }pd(p);int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),a,b);if(r>=mid+1)modify(l,r,mid+1,t,rs(p),a,b);pu(p); }void upd(int l,int s,int t,int p){ if(s==t){ x(p).mn-=inf,x(p).mn+=R[s].r+1; x(p).mx+=inf;x(p).mx+=R[s].l; x(p).res=x(p).mn-x(p).mx; return; }pd(p);int mid=s+t>>1; if(l<=mid)upd(l,s,mid,ls(p));else upd(l,mid+1,t,rs(p));pu(p); }void upd2(int l,int s,int t,int p){ if(s==t){ x(p).mn=inf,x(p).mx=-inf,x(p).res=2*inf; return; }pd(p);int mid=s+t>>1; if(l<=mid)upd2(l,s,mid,ls(p));else upd2(l,mid+1,t,rs(p));pu(p); } }T; bool chk(int pos,int w){ /*p[M]=w; int L=0; for(auto it:vec){ L=max(L,it.p1.p1)+p[it.p2]; if(it.p1.p2-L+1<0)return 0; }return 1;*/ T.modify(pos,m,1,m,1,-w,0); T.modify(pos+1,m,1,m,1,0,-w); bool ok=(T.x(1).res>=0); T.modify(pos,m,1,m,1,w,0); T.modify(pos+1,m,1,m,1,0,w); return ok; } void slv(){ n=read(); up(i,1,n)a[i]=read(),s[i]=s[i-1]+a[i]; m=read(); up(i,1,m)d[i].l=read(),d[i].r=read(),d[i].k=read(),d[i].fl=d[i].l,d[i].l=s[d[i].l-1]+1,d[i].r=s[d[i].r]; up(i,1,m)R[i].l=d[i].l,R[i].r=d[i].r,R[i].fl=d[i].fl; sort(R+1,R+m+1); T.bd(1,m,1); up(i,1,m){ int l=d[i].l,r=d[i].r,k=d[i].k; int pos=lower_bound(R+1,R+m+1,(Range){d[i].l,d[i].r,d[i].fl})-R; T.upd(pos,1,m,1); int L=0,R=k+1; if(!chk(pos,0))R=1; while(L+1<R){ int mid=L+R>>1; if(chk(pos,mid))L=mid; else R=mid; } p[i]=L;printf("%d\n",L); //cout<<"res: "<<T.x(1).res<<endl; T.modify(pos,m,1,m,1,-L,0); T.modify(pos+1,m,1,m,1,0,-L); if(!L)T.upd2(pos,1,m,1); //cout<<"res: "<<T.x(1).res<<endl; } }int main(){ //freopen("flandre.in","r",stdin); //freopen("flandre.out","w",stdout); slv(); fclose(stdin); fclose(stdout); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }