#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 300010;
int n, tag[maxn << 2];
bool mark[maxn << 2];
struct node { int mx, freq, sec; ll sum; } t[maxn << 2];
node operator + (node A, node B) {
if (A.mx < B.mx) swap(A, B);
if (A.mx > B.mx) return {A.mx, A.freq, max(A.sec, B.mx), A.sum + B.sum};
return {A.mx, A.freq + B.freq, max(A.sec, B.sec), A.sum + B.sum};
}
node apply(node A, int k) {
return {min(A.mx, k), A.freq, A.sec, A.sum - 1LL * A.freq * max(0, A.mx - k)};
}
#define mid ((l + r) >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
void apply(int k, int v) {
if (mark[k]) {
int x = min(v, t[k].mx);
t[k] = {x, 1, (int)-1e9, x};
} else if (v > t[k].sec && v < tag[k]) {
t[k] = apply(t[k], tag[k] = v);
} else if (v <= t[k].sec) {
apply(ls, v), apply(rs, v);
t[k] = t[ls] + t[rs], tag[k] = INT_MAX;
}
}
void pushdown(int k) {
apply(ls, tag[k]), apply(rs, tag[k]), tag[k] = INT_MAX;
}
void build(int k, int l, int r, int *h) {
tag[k] = INT_MAX;
if (l == r) { t[k] = {h[l], 1, (int)-1e9, h[l]}, mark[k] = 1; return; }
build(ls, l, mid, h), build(rs, mid + 1, r, h);
t[k] = t[ls] + t[rs];
}
void upd(int k, int l, int r, int p, int v) {
if (l == r) { t[k] = {v, 1, (int)-1e9, v}; return; }
pushdown(k);
mid >= p ? upd(ls, l, mid, p, v) : upd(rs, mid + 1, r, p, v);
t[k] = t[ls] + t[rs];
}
void modify(int k, int l, int r, int ql, int qr, int v) {
if (l >= ql && r <= qr) return apply(k, v);
pushdown(k);
if (mid >= ql) modify(ls, l, mid, ql, qr, v);
if (mid < qr) modify(rs, mid + 1, r, ql, qr, v);
t[k] = t[ls] + t[rs];
}
int find(int k, int l, int r, int ql, int qr, int v1, int &v2) {
if (t[k].mx < v1) return 0;
if (l >= ql && r <= qr && t[k].freq < v2) return v2 -= t[k].freq, 0;
if (l == r) return l;
pushdown(k);
int t = 0;
if (mid >= ql) t = find(ls, l, mid, ql, qr, v1, v2);
if (mid < qr && !t) t = find(rs, mid + 1, r, ql, qr, v1, v2);
return t;
}
node query(int k, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr) return t[k];
pushdown(k);
if (mid >= qr) return query(ls, l, mid, ql, qr);
if (mid < ql) return query(rs, mid + 1, r, ql, qr);
return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
}
void initialise(int _n, int, int *h) {
build(1, 1, n = _n, h);
}
void cut(int l, int r, int k) {
while (k) {
auto p = query(1, 1, n, l, r);
ll rem = 1LL * (p.mx - p.sec) * p.freq;
if (rem <= k) {
modify(1, 1, n, l, r, max(0, p.sec)), k -= rem;
} else {
int need = k % p.freq;
int i = need ? find(1, 1, n, l, r, p.mx, need) : l - 1;
if (i >= l) modify(1, 1, n, l, i, max(0, p.mx - k / p.freq - 1));
modify(1, 1, n, i + 1, r, max(0, p.mx - k / p.freq)); break;
}
}
}
void magic(int i, int x) {
upd(1, 1, n, i, x);
}
ll inspect(int l, int r) {
return query(1, 1, n, l, r).sum;
}
