#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int qmax = 2e5 + 5;
const int nmax = 2e5 + 5;
namespace DS {
int v[qmax];
int Q;
void upd(int p, int x) {
v[p] += x;
}
int solve(int C) {
int p = -1, mn = 0;
int sum = 0;
for(int i = 0; i < Q; i++) {
sum += v[i];
if(sum <= mn) mn = sum, p = i;
}
vector<int> a, bad, nxtbad;
a.emplace_back(0);
for(int i = p + 1; i < Q; i++) a.emplace_back(a.back() + v[i]);
vector<int> mx;
mx.emplace_back(0);
for(auto x : a | views::reverse) mx.emplace_back(max(mx.back(), x));
reverse(all(mx));
bad.assign(sz(a), 0);
nxtbad.assign(sz(a), 0);
mn = a.back();
for(int i = sz(a) - 1; i >= 0; i--) {
mn = min(mn, a[i]);
if(mn == a[i]) bad[i] = 1, nxtbad[i] = mn;
else nxtbad[i] = nxtbad[i + 1];
}
int rez = a.back();
for(int i = 0; i < sz(a); i++) {
if(bad[i]) mn = a[i];
if(mx[i] >= C) rez = min(rez, a.back() - min(mx[i] - C, nxtbad[i]));
else break;
}
return max(rez, 0);
}
}
vector<pii> opers[nmax];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
DS::Q = sz(l);
for(int i = 0; i < sz(l); i++) {
opers[l[i]].emplace_back(i, v[i]);
opers[r[i] + 1].emplace_back(i, -v[i]);
}
vector<int> rez;
for(int i = 0; i < sz(c); i++) {
for(auto [p, x] : opers[i]) DS::upd(p, x);
rez.emplace_back(DS::solve(c[i]));
}
return rez;
}
/**
vreau sa ma tai
--
*/
