#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--) {
nxtbad[i] = min(mn, a[i]);
}
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;
}
/**
1) Din punctul de vedere al datului cu capu de podea, suma minima pe prefix este un punct bun de inceput
* 0 13 4 7 20 9 12 10
* fie caderea la:
* 0 13 4 7 13 2 5 3
* si daca primul 13 ar fi gatuit de 1 sau cv mic rau, daca scadem din el:
* 0 12 3 6 12 1 4 3
*
*
* sau daca il ignoram:
* 0 (13 4 7) 12 1 5 3
*
* gatuirea ori e facuta la primul 13 iar apoi la al doilea ori direct la al doilea => chiar nu cont, de interes este deci urm maxim
* as fi tentat chiar sa spun ca:
*
* tehnic vorbind gatuirile nu se intampla una dupa alta (i.e. ai geva ca in cazul asta 4 care nu ajunge niciodata in mod relevant la 0)
*
* Dar daca o gatuire de 9 se face si avea una de 7 inainte, atunci putem spune ca efectul final (care e de macar -9 pe final) e subiectul unei telescopari de la gatuirea intai pana la 7, apoi ce a ramas din 9 dupa asta (-2 + -7 = -9)
* In fine
* sa zicem ca (cumva) nsh ce gatuire se intampla.
*
* Ma gandesc ca singura conditie e ca nimic de dupa sa fie gen prea mare?
* si doar caut binar asa ceva?
* bine, ultima gatuire a.i. ceva de dupa e prea mare
* apoi scad diferenta
*
* de ce e asa de penal in retrospectiva??
*
*
--
*/
