#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
const li inf=1e18;
li mn[550001],mx[550001],upd[550001];
int l[550001],r[550001],k=1;
void Upd(int p)
{
mn[p]+=upd[p],mx[p]+=upd[p];
if (p<k) upd[2*p]+=upd[p],upd[2*p+1]+=upd[p];
upd[p]=0;
}
void Add(int p, int ll, int rr, int x)
{
if (rr<l[p] || ll>r[p]) Upd(p);
else if (ll<=l[p] && rr>=r[p]) upd[p]+=x,Upd(p);
else Upd(p),Add(2*p,ll,rr,x),Add(2*p+1,ll,rr,x),mn[p]=min(mn[2*p],mn[2*p+1]),mx[p]=max(mx[2*p],mx[2*p+1]);
}
vector<int> cvorovi;
void rastavi(int p, int ll, int rr)
{
if (ll>r[p] || rr<l[p]) return;
if (ll<=l[p] && rr>=r[p]) Upd(p),cvorovi.pb(p);
else Upd(p),rastavi(2*p,ll,rr),rastavi(2*p+1,ll,rr);
}
int WalkRaz(int p, int x, li tmn, li tmx)
{
Upd(p);
if (max(tmx,mx[p])-min(tmn,mn[p])<x) return -1;
if (p>=k) return p-k;
int mozda=WalkRaz(2*p+1,x,tmn,tmx);
if (mozda==-1) return WalkRaz(2*p,x,min(tmn,mn[2*p+1]),max(tmx,mx[2*p+1]));
return mozda;
}
int WalkMin(int p)
{
Upd(p);
if (p>=k) return p-k;
Upd(2*p),Upd(2*p+1);
if (mn[p]==mn[2*p+1]) return WalkMin(2*p+1);
return WalkMin(2*p);
}
int WalkMax(int p)
{
Upd(p);
if (p>=k) return p-k;
Upd(2*p),Upd(2*p+1);
if (mx[p]==mx[2*p+1]) return WalkMax(2*p+1);
return WalkMax(2*p);
}
void ispisi()
{
ff(i,1,2*k) Upd(i);
for (int kk=1;kk<=k;kk*=2)
{
ff(i,kk,2*kk) cout<<"("<<mn[i]<<","<<mx[i]<<") ";
cout<<endl;
} cout<<endl;
}
vector<pair<bool,pii>> qry[200005]; //add (or remove) : time kad dodajemo : sta dodajemo (potenicjalno negativno)
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V)
{
int n=(int)C.size();
int q=(int)V.size();
while (k<q) k*=2;
ff(i,0,k) l[i+k]=i,r[i+k]=i;
bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
ff(i,q,k) mn[i+k]=inf,mx[i+k]=-inf;
bff(i,1,k) mn[i]=min(mn[2*i],mn[2*i+1]);
bff(i,1,k) mx[i]=max(mx[2*i],mx[2*i+1]);
ff(i,0,q)
{
qry[L[i]].pb({1,{i,V[i]}});
qry[R[i]+1].pb({0,{i,V[i]}});
}
vector<int> ans(n,0);
li suma=0;
ff(i,0,n)
{
for (auto it : qry[i])
{
bool dodajem=it.xx;
int kad=it.yy.xx;
int sta=it.yy.yy;
if (dodajem) Add(1,kad,q-1,sta),suma+=sta;
else Add(1,kad,q-1,-sta),suma-=sta;
}
Upd(1);
//ispisi();
if (mx[1]-mn[1]<=C[i])
{
if (mx[1]>C[i]) ans[i]=C[i]-(mx[1]-suma);
else
{
int djemin=WalkMin(1);
if (mn[djemin+k]<0) ans[i]=suma-mn[djemin+k];
else ans[i]=suma;
}
}
else
{
int dje=WalkRaz(1,C[i],inf,-inf);
rastavi(1,dje,q-1);
int mp=cvorovi[0];
for (auto p : cvorovi) if (mn[p]<mn[mp]) mp=p;
int djemin=WalkMin(mp);
mp=cvorovi[0];
for (auto p : cvorovi) if (mx[p]>mx[mp]) mp=p;
int djemax=WalkMax(mp);
cvorovi.clear();
if (djemin>djemax) ans[i]=min((li)C[i],suma-mn[djemin+k]);
else ans[i]=max(0ll,C[i]-(mx[djemax+k]-suma));
}
}
return ans;
}
