#include<bits/stdc++.h>
using namespace std;
long long c[200010];
struct node{long long mini, maxi, lazy;};
const int base = 1<<18;
node tree[2*base];
void push(int w){
if(w>=base)return;
tree[w*2].lazy+=tree[w].lazy;
tree[w*2+1].lazy+=tree[w].lazy;
tree[w*2].mini+=tree[w].lazy;
tree[w*2].maxi+=tree[w].lazy;
tree[w*2+1].mini+=tree[w].lazy;
tree[w*2+1].maxi+=tree[w].lazy;
tree[w].lazy = 0;
}
void update(int w, int l, int p, int a, int b, long long val){
push(w);
if(l>b || p<a)return;
if(a<=l && p<=b){
tree[w].lazy+=val;
tree[w].maxi+=val;
tree[w].mini+=val;
return;
}
update(w*2, l, (l+p)/2, a, b, val);
update(w*2+1, (l+p)/2+1, p, a, b, val);
tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
long long maxi(int w, int l, int p, int a, int b){
push(w);
if(l>b || p<a)return -1000000000000000000;
if(a<=l && p<=b){
return tree[w].maxi;
}
return max(maxi(w*2, l, (l+p)/2, a, b), maxi(w*2+1, (l+p)/2+1, p, a, b));
// tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
// tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
long long mini(int w, int l, int p, int a, int b){
push(w);
if(l>b || p<a)return 1000000000000000000;
if(a<=l && p<=b){
return tree[w].mini;
}
return min(mini(w*2, l, (l+p)/2, a, b), mini(w*2+1, (l+p)/2+1, p, a, b));
// tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
// tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
vector<int> distribute_candies(vector<int>C, vector<int>l, vector<int>r, vector<int> V)
{
vector<int>ans;
int n, q, i, a, b, v;
n = C.size();
for(i=0;i<n;i++)
c[i] = C[i];
q = l.size();
vector<pair<int,pair<int,int>>>sorted;
for(i=1;i<=q;i++){
a = l[i-1];
b = r[i-1];
v = V[i-1];
scanf("%d%d%d", &a, &b, &v);
sorted.push_back({a, {i, v}});
sorted.push_back({b+1, {i, -v}});
}
for(i=q+1;i<base;i++){
tree[base+i].mini = 1000000000000000000;
tree[base+i].maxi = -1000000000000000000;
}
for(i=base-1;i>0;i--){
tree[i].maxi = max(tree[i*2].maxi, tree[i*2+1].maxi);
tree[i].mini = min(tree[i*2].mini, tree[i*2+1].mini);
}
sort(sorted.begin(), sorted.end());
int it = 0;
for(i=0;i<n;i++){
while(it<(int)sorted.size() && sorted[it].first==i){
update(1, 0, base-1, sorted[it].second.first, q, sorted[it].second.second);
it++;
}
int p;
if(tree[1].maxi-tree[1].mini>=c[i]){
int w = 1;
long long sufMAX = -1000000000000000000, sufMIN = 1000000000000000000;
while(w<base){
push(w);
if(max(sufMAX, tree[w*2+1].maxi)-min(sufMIN, tree[w*2+1].mini)>=c[i])
w = w*2+1;
else{
sufMAX = max(sufMAX, tree[w*2+1].maxi);
sufMIN = min(sufMIN, tree[w*2+1].mini);
w = w*2;
}
}
p = w-base;
}
else{
p = -1;
}
if(p==-1)
ans.push_back(mini(1, 0, base-1, q, q)-mini(1, 0, base-1, 0, q));
else{
if(mini(1, 0, base-1, p, q)==mini(1, 0, base-1, p, p))
ans.push_back(mini(1, 0, base-1, q, q)-maxi(1, 0, base-1, p, q)+c[i]);
else
ans.push_back(mini(1, 0, base-1, q, q)-mini(1, 0, base-1, p, q));
}
}
return ans;
}
