// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
#define nl '\n'
template<class T> using V = vector<T>;
using ll = long long;
const int nax = (1 << 19);
const int INF = 1e9 + 10;
struct T {
int mx = -1, amt = 0;
int mx2 = -1, amt2 = 0;
ll sum = 0;
};
T seg[2 * nax];
int lzy[2 * nax]; // value that mx is reduced to
T comb(T a, T b) {
T c;
map<int, int> C;
C[a.mx] += a.amt; C[a.mx2] += a.amt2;
C[b.mx] += b.amt; C[b.mx2] += b.amt2;
tie(c.mx, c.amt) = *rbegin(C); C.erase(prev(end(C)));
tie(c.mx2, c.amt2) = *rbegin(C); C.erase(prev(end(C)));
c.sum = a.sum + b.sum;
return c;
}
void pull(int x) { seg[x] = comb(seg[2 * x], seg[2 * x + 1]); }
void push(int x, int L, int R) {
if (lzy[x] < seg[x].mx) {
seg[x].sum -= (seg[x].mx - lzy[x]) * 1LL * seg[x].amt;
seg[x].mx = lzy[x];
if (L != R) for(int i = 0; i < 2; i++) lzy[2 * x + i] = lzy[x];
}
lzy[x] = INF;
}
void upd(int l, int r, int v, int x = 1, int L = 0, int R = nax - 1) {
push(x, L, R); if (r < L || R < l || seg[x].mx <= v) return;
// cout << l << " " << r << " -> " << L << " " << R << " -> " << v << endl;
// cout << seg[x].mx << " " << seg[x].mx2 << endl;
if (l <= L && R <= r && seg[x].mx2 < v) {
// cout << "LZY" << endl;
lzy[x] = v; push(x, L, R);
return;
}
int M = (L + R) / 2;
upd(l, r, v, 2 * x, L, M);
upd(l, r, v, 2 * x + 1, M + 1, R);
pull(x);
}
// int find(int l, int r, int v, int k, int x = 1, int L = 0, int R = nax - 1) {
// push(x, L, R); if (r < L || R < l || seg[x].mx < v) return -1;
// if (L == R) return L;
// if (l <= L && R <= r && seg[x].amt < k) return -seg[x].amt;
// int M = (L + R) / 2;
// int res = find(l, r, v, k, 2 * x, L, M);
// if (res < 0) res = find(l, r, v, k - res, 2 * x + 1, M + 1, R);
// return res;
// }
void updx(int p, int v, int x = 1, int L = 0, int R = nax - 1) {
push(x, L, R); if (p < L || R < p) return;
if (L == R) {
// cout << L << " -> " << v << endl;
seg[x] = T{v, 1, -1, 0, v};
return;
}
int M = (L + R) / 2;
updx(p, v, 2 * x, L, M);
updx(p, v, 2 * x + 1, M + 1, R);
pull(x);
}
T qry(int l, int r, int x = 1, int L = 0, int R = nax - 1) {
push(x, L, R); if (r < L || R < l) return T();
// cout << x << " " << L << " " << R << " --> " << seg[x].mx << " " << seg[x].amt << " " << seg[x].sum << endl;
if (l <= L && R <= r) return seg[x];
int M = (L + R) / 2;
return comb(qry(l, r, 2 * x, L, M), qry(l, r, 2 * x + 1, M + 1, R));
}
void initialise(int N, int Q, int h[]) {
for(int i = 0; i < 2 * nax; i++) seg[i] = T(), lzy[i] = INF;
for(int i = 0; i < N; i++) updx(i, h[i + 1]);
// cout << "INIT COMPLETE" << endl;
}
void cut(int l, int r, int k) {
--l, --r;
// cout << "CUT: " << l << " " << r << " " << k << endl;
while(1) {
T res = qry(l, r);
if (res.mx == 0) return;
res.mx2 = max(res.mx2, 0);
// cout << res.mx << " " << res.amt << endl;
ll need = (res.mx - res.mx2) * 1LL * res.amt;
// cout << need << endl;
if (need <= k) {
upd(l, r, res.mx2);
k -= need;
} else {
int dec = k / res.amt;
upd(l, r, res.mx - dec);
k %= res.amt;
break;
}
}
// cout << "LEFT: " << k << endl;
if (k) {
// assert(false);
T all = qry(l, r);
int lo = l, hi = r;
while(lo < hi) {
int mid = (lo + hi + 1) / 2;
T res = qry(l, mid);
int cnt = (res.mx == all.mx ? res.amt : 0);
if (cnt <= k) lo = mid;
else hi = mid - 1;
}
int bnd = lo;
assert(qry(l, bnd).amt == k);
// cout << "BND: " << bnd << endl;
upd(l, bnd, all.mx - 1);
}
//
// cout << "DONE" << endl;
}
void magic(int i, int x) {
--i;
// cout << "MAGIC: " << i << " " << x << endl;
updx(i, x);
// cout << "DONE" << endl;
}
long long inspect(int l, int r) {
--l, --r;
// cout << "INSPECT: " << l << " " << r << endl;
return qry(l, r).sum;
}
// g++-13 -DEVAL -O2 -std=c++17 grader.cpp A.cpp -o G
