#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int L = 0x3f3f3f3f;
struct P
{
int mx, freq, mx2;
ll sum;
};
P operator + (const P &a, const P& b)
{
P p;
if (a.mx == b.mx)
{
p.mx = a.mx;
p.mx2 = max(a.mx2, b.mx2);
p.freq = a.freq + b.freq;
}else if (a.mx > b.mx)
{
p.mx = a.mx;
p.mx2 = max(a.mx2, b.mx);
p.freq = a.freq;
}else{
p.mx = b.mx;
p.mx2 = max(a.mx, b.mx2);
p.freq = b.freq;
}
p.sum = a.sum + b.sum;
return p;
}
struct Node
{
int lc, rc;
P p;
int lazy;
};
Node nodes[5000000];
int new_node()
{
static int upto = 0;
auto &node = nodes[++upto];
node.lazy = L;
return upto;
}
void clean(int i)
{
auto &node = nodes[i];
if (not node.lc)
{
node.lc = new_node();
node.rc = new_node();
}
if (node.lazy >= node.p.mx)
{
node.lazy = L;
return;
}
node.p.sum -= (ll) node.p.freq * (node.p.mx - node.lazy);
node.p.mx = node.lazy;
nodes[node.lc].lazy = min(nodes[node.lc].lazy, node.lazy);
nodes[node.rc].lazy = min(nodes[node.rc].lazy, node.lazy);
node.lazy = L;
}
void upd(int i, int l, int r, int p, int x)
{
auto &node = nodes[i];
clean(i);
if (p < l or p > r)
return;
if (l == r)
{
node.p.mx = x, node.p.freq = 1, node.p.mx2 = 0, node.p.sum = x;
return;
}
int m = l + (r - l) / 2;
upd(node.lc, l, m, p, x);
upd(node.rc, m + 1, r, p, x);
node.p = nodes[node.lc].p + nodes[node.rc].p;
}
void cap(int i, int l, int r, int ql, int qr, int x)
{
auto &node = nodes[i];
clean(i);
if (qr < l or ql > r)
return;
if ((ql <= l and qr >= r and x > node.p.mx2) or l == r)
{
node.lazy = x;
clean(i);
return;
}
int m = l + (r - l) / 2;
cap(node.lc, l, m, ql, qr, x);
cap(node.rc, m + 1, r, ql, qr, x);
node.p = nodes[node.lc].p + nodes[node.rc].p;
}
P query(int i, int l, int r, int ql, int qr)
{
auto &node = nodes[i];
clean(i);
if (qr < l or ql > r)
return {0, 0, 0, 0};
if (ql <= l and qr >= r)
return node.p;
int m = l + (r - l) / 2;
return query(node.lc, l, m, ql, qr) + query(node.rc, m + 1, r, ql, qr);
}
int N;
int root = new_node();
void initialise(int N, int Q, int h[])
{
::N = N;
for (int i = 1; i <= N; i++)
{
upd(root, 1, N, i, h[i]);
}
}
void cut(int l, int r, int k)
{
if (k <= 0) return;
auto p = query(root, 1, N, l, r);
int g = min<ll>(k, (ll) p.freq * (p.mx - p.mx2));
if (p.mx == 0) return;
int pi = g % p.freq;
int pc = g / p.freq;
if (pi == 0)
{
cap(root, 1, N, l, r, p.mx - pc);
}else{
int a = l, b = r + 1;
while (b - a > 1)
{
int m = a + (b - a) / 2;
auto f = query(root, 1, N, l, m - 1);
if ((f.mx == p.mx ? f.freq : 0) >= pi)
{
b = m;
}else{
a = m;
}
}
#ifdef DEBUG
auto d = query(root, 1, N, l, a);
cout << "D: " << l << ' ' << a << ' ' << r << ' ' << d.freq << ' ' << d.mx << endl;
#endif
cap(root, 1, N, l, a, p.mx - pc - 1);
cap(root, 1, N, a + 1, r, p.mx - pc);
}
cut(l, r, k - g);
}
void magic(int i, int x)
{
upd(root, 1, N, i, x);
}
ll inspect(int l, int r)
{
return query(root, 1, N, l, r).sum;
}
