// 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;
if (a.mx == b.mx) {
c.mx = a.mx; c.amt = a.amt + b.amt;
c.mx2 = max(a.mx2, b.mx2);
c.amt2 = (c.mx2 == a.mx2 ? a.amt2 : 0) + (c.mx2 == b.mx2 ? b.amt2 : 0);
} else if (a.mx > b.mx) {
c.mx = a.mx; c.amt = a.amt;
c.mx2 = max(a.mx2, b.mx);
c.amt2 = (c.mx2 == a.mx2 ? a.amt2 : 0) + (c.mx2 == b.mx ? b.amt : 0);
} else {
c.mx = b.mx; c.amt = b.amt;
c.mx2 = max(a.mx, b.mx2);
c.amt2 = (c.mx2 == a.mx ? a.amt : 0) + (c.mx2 == b.mx2 ? b.amt2 : 0);
}
// 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 || !k) return -1;
if (l <= L && R <= r) { // in the range (mx <= v, mx !< v => mx == v)
// cout << L << " " << R << " " << seg[x].mx << " " << seg[x].amt << " " << v << " -> " << k << endl;
if (seg[x].amt < k) {
k -= seg[x].amt;
return -1;
}
if (L == R) {
// cout << "FOUND: " << L << " " << seg[x].mx << " " << seg[x].amt << " " << v << " -> " << k << endl;
// k = 0;
return L;
}
// otherwise continue search
}
int M = (L + R) / 2;
int res = find(l, r, v, k, 2 * x, L, M);
int res2 = find(l, r, v, k, 2 * x + 1, M + 1, R);
return (res == -1 ? res2 : 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) / 2;
// T res = qry(l, mid);
// int cnt = (res.mx == all.mx ? res.amt : 0);
// if (cnt >= k) hi = mid;
// else lo = mid + 1;
// }
// int bnd = lo;
// assert(qry(l, bnd).amt == k);
int bnd = find(l, r, all.mx, k);
// cout << "BND: " << bnd << " <--> " << lo << 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
