#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]; struct node {int l,r,k,id;}O[300400]; inline bool cmp(node A,node B){ return A.l<B.l; } inline bool cmpid(node A,node B){ return A.id<B.id; } vector<pii>P[300040]; inline bool cmpp(pii A,pii B){ return p1(A)<p1(B); } int l[300300],r[300300]; map<int,int>mp[300400]; priority_queue<int>Q[300040]; int mx[300300<<2]; int id[300300]; #define lc(x) (x<<1) #define rc(x) (x<<1|1) inline int C(int a,int b){ if(Q[a].top()>Q[b].top())return a; return b; } inline void upd(int x){ mx[x]=C(mx[lc(x)],mx[rc(x)]); } inline void bd(int x,int l,int r){ if(l==r){ id[l]=x; mx[x]=l; return ; } int mid=l+r>>1; bd(lc(x),l,mid); bd(rc(x),mid+1,r); upd(x); } inline int g(int x,int l,int r,int L,int R){ // cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<mx[x]<<endl; if(L<=l&&r<=R)return mx[x]; int mid=l+r>>1; if(R<=mid)return g(lc(x),l,mid,L,R); if(L>mid)return g(rc(x),mid+1,r,L,R); return C(g(lc(x),l,mid,L,R),g(rc(x),mid+1,r,L,R)); } inline void fls(int p){ int x=id[p]; while(Q[p].top()!=-1&&!mp[p][Q[p].top()])Q[p].pop(); mx[x]=p; // cerr<<p<<" "<<x<<endl; // cerr.flush(); while(x!=1){ x>>=1; // cerr<<x<<" "<<lc(x)<<" "<<rc(x)<<" "<<mx[lc(x)]<<" "<<mx[rc(x)]<<endl;; // cerr.flush(); upd(x); // cout<<x<<" "<<mx[x]<<endl; } // cerr<<"!"; // cerr.flush(); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("flandre.in","r",stdin); // freopen("flandre.out","w",stdout); // system("grep VmPeak /proc/$PPID/status"); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; cin>>q; for(int i=1;i<=q;i++) cin>>O[i].l>>O[i].r>>O[i].k,O[i].id=i; sort(O+1,O+q+1,cmp); int p=0; for(int i=1;i<=q;i++){ int e=O[i].k; while(p<O[i].l)p++; l[O[i].id]=p; while(p<=O[i].r){ int t=min(e,a[p]); a[p]-=t; e-=t; P[p].push_back({O[i].id,t}); if(a[p])break; p++; } r[O[i].id]=min(p,O[i].r); } Q[0].push(-1); for(int i=1;i<=n;i++){ if(a[i])P[i].push_back({q+1,a[i]}); // sort(P[i].begin(),P[i].end(),cmpp); Q[i].push(-1); for(pii e:P[i]) mp[i][p1(e)]=p2(e),Q[i].push(p1(e)); // if(60<=i&&i<=71){ // for(pii e:P[i]) // cout<<i<<" "<<p1(e)<<" "<<p2(e)<<endl; // } // if(P[i].size())cout<<Q[i].top()<<" "; } sort(O+1,O+q+1,cmpid); bd(1,1,n); // return 0; for(int i=1;i<=q;i++){ int s=0; for(int j=l[i];j<=r[i];j++) s+=mp[j][i],mp[j][i]=0; int rem=O[i].k-s; while(rem){ int x=g(1,1,n,O[i].l,O[i].r); // cout<<"!"<<x<<endl; if(Q[x].top()==-1)break; int y=Q[x].top(); int t=min(mp[x][y],rem); s+=t; rem-=t; mp[x][y]-=t; // cout<<x<<" "<<y<<" "<<t<<" "<<rem<<endl; fls(x); } cout<<s<<endl; } cout.flush(); return 0; }