#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define INFI (ll)1000000000000000000
struct segTree{
ll l; ll r;
segTree *lc, *rc;
pair<ll, ll> mx;
pair<ll, ll> mn;
ll lazy;
segTree(ll st){
l = r = st;
lc = rc = nullptr;
mx = mn = {0, st};
lazy = 0;
}
segTree(segTree * le, segTree * ri){
lc = le; rc = ri;
mx = max(lc->mx, rc->mx);
mn = min(lc->mn, rc->mn);
lazy = 0;
l = le->l;
r = ri->r;
}
};
segTree * build (ll l, ll r){
if(l == r) return new segTree(l);
return new segTree(build(l, (l+r)/2), build((l+r)/2 + 1, r));
}
void update(ll l, ll r, ll x, segTree*st){
if(st->l == st->r){
st->mn.first += x + st->lazy;
st->mx.first += x + st->lazy;
st->lazy = 0;
return;
}
if(st->l == l && st->r == r){
st->lc->lazy += x + st->lazy;
st->rc->lazy += x + st->lazy;
st->mn.first += x + st->lazy;
st->mx.first += x + st->lazy;
st->lazy = 0;
return;
}
ll mid = (st->l + st->r)/2;
if(l<=mid) update(l, min(r, mid), x, st->lc);
if(r>mid) update(max(mid+1, l), r, x, st->rc);
st->mn = min(st->lc->mn, st->rc->mn);
st->mx = max(st->lc->mx, st->rc->mx);
}
pair<ll, ll> query(ll md, ll l, ll r, segTree * st){
st->mn.first += st->lazy;
st->mx.first += st->lazy;
if(st->l != st->r){
st->lc->lazy += st->lazy;
st->rc->lazy += st->lazy;
}
st->lazy = 0;
// if(l == st->l && st->r == r){
// if(md == 0) return st->mn;
// else return st->mx;
// }
if(st->l == st->r){
if(md == 0) return st->mn;
else return st->mx;
}
ll mid = (st->l + st->r)/2;
if(md == 0){
pair<ll, ll> ans = {INFI, INFI};
if(l <= mid) ans = min(ans, query(md, l, min(r, mid), st->lc));
if(r > mid) ans = min(ans, query(md, max(l, mid+1), r, st->rc));
return ans;
}
//if(md == 1){
pair<ll, ll> ans = {-INFI, -INFI};
if(l <= mid) ans = max(ans, query(md, l, min(r, mid), st->lc));
if(r > mid) ans = max(ans, query(md, max(l, mid+1), r, st->rc));
return ans;
//}
}
vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v){
ll q = v.size();
vector<pair<ll, pair<ll, ll>>> updL;
for(ll i = 0; i<q; i++){
updL.push_back({l[i], {i+2, v[i]}});
}
vector<pair<ll, pair<ll, ll>>> updR;
for(ll i = 0; i<q; i++){
updR.push_back({r[i], {i+2, v[i]}});
}
sort(updL.begin(), updL.end());
sort(updR.begin(), updR.end());
segTree * st = build(0, q+1);
update(0, 0, INFI, st);
vector<int> ans;
for(ll i = 0; i<C.size(); i++){
ll c = C[i];
ll le = upper_bound(updL.begin(), updL.end(), make_pair(i-1, make_pair(INFI, INFI))) - updL.begin();
ll ri = upper_bound(updL.begin(), updL.end(), make_pair(i, make_pair(INFI, INFI))) - updL.begin()-1;
for(ll j = le; j<=ri; j++) update(updL[j].second.first, q+1, updL[j].second.second, st);
le = upper_bound(updR.begin(), updR.end(), make_pair(i-2, make_pair(INFI, INFI))) - updR.begin();
ri = upper_bound(updR.begin(), updR.end(), make_pair(i-1, make_pair(INFI, INFI))) - updR.begin()-1;
for(ll j = le; j<=ri; j++) update(updR[j].second.first, q+1, -updR[j].second.second, st);
pair<ll, ll> qmx = query(1, 0, q+1, st);
pair<ll, ll> qmn = query(0, 0, q+1, st);
if(qmx.first <= c && qmn.first >=0){
ans.push_back(query(1, q+1, q+1, st).second);
continue;
}
le = 0; ri = q+1;
while(le<ri){
ll mid = (le + ri+1)/2;
auto maxInRange = query(1, mid, q+1, st);
auto minInRange = query(0, mid, q+1, st);
if(maxInRange.first - minInRange.first >= c) le = mid;
else ri = mid-1;
}
auto maxInRange = query(1, le, q+1, st);
auto minInRange = query(0, le, q+1, st);
if(maxInRange.second > minInRange.second) ans.push_back(query(0, q+1, q+1, st).first - query(0, maxInRange.second, maxInRange.second, st).first + c);
else ans.push_back(query(0, q+1, q+1, st).first - query(0, minInRange.second, minInRange.second, st).first);
}
return ans;
}
