#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1e9 + 7;
constexpr int R = 1 << 19;
struct Node {
int mx, cnt_mx;
int mx2;
long long sum;
int assign_mn;
Node() {
mx = mx2 = -1;
cnt_mx = 0;
sum = 0;
assign_mn = INF;
}
Node operator+(Node b) {
Node c;
c.mx = max(mx, b.mx);
if (c.mx == mx) {
c.cnt_mx += cnt_mx;
c.mx2 = max(c.mx2, mx2);
} else {
c.mx2 = max(c.mx2, mx);
}
if (c.mx == b.mx) {
c.cnt_mx += b.cnt_mx;
c.mx2 = max(c.mx2, b.mx2);
} else {
c.mx2 = max(c.mx2, b.mx);
}
c.sum = sum + b.sum;
return c;
}
};
Node tree[R * 2];
void build() {
for (int i = R - 1; i > 0; --i) {
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
}
void push(int node) {
if (tree[node].assign_mn != INF) {
if (tree[node * 2].mx > tree[node].assign_mn) {
tree[node * 2].sum -= (tree[node * 2].mx - tree[node].assign_mn) * 1LL * tree[node * 2].cnt_mx;
tree[node * 2].mx = tree[node].assign_mn;
tree[node * 2].assign_mn = tree[node].assign_mn;
}
if (tree[node * 2 + 1].mx > tree[node].assign_mn) {
tree[node * 2 + 1].sum -= (tree[node * 2 + 1].mx - tree[node].assign_mn) * 1LL * tree[node * 2 + 1].cnt_mx;
tree[node * 2 + 1].mx = tree[node].assign_mn;
tree[node * 2 + 1].assign_mn = tree[node].assign_mn;
}
}
tree[node].assign_mn = INF;
}
void assign_mn(int ql, int qr, int val, int node = 1, int nl = 0, int nr = R) {
if (qr <= nl || nr <= ql || tree[node].mx <= val) {
return;
}
if (ql <= nl && nr <= qr && tree[node].mx2 < val) {
tree[node].sum -= (tree[node].mx - val) * 1LL * tree[node].cnt_mx;
tree[node].mx = val;
tree[node].assign_mn = val;
return;
}
push(node);
int nm = (nl + nr) / 2;
assign_mn(ql, qr, val, node * 2, nl, nm);
assign_mn(ql, qr, val, node * 2 + 1, nm, nr);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void assign_pos(int pos, int val, int node = 1, int nl = 0, int nr = R) {
if (nl == nr - 1) {
tree[node].mx = tree[node].sum = val;
return;
}
push(node);
int nm = (nl + nr) / 2;
if (pos < nm) {
assign_pos(pos, val, node * 2, nl, nm);
} else {
assign_pos(pos, val, node * 2 + 1, nm, nr);
}
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
Node get(int ql, int qr, int node = 1, int nl = 0, int nr = R) {
if (ql <= nl && nr <= qr) {
return tree[node];
}
if (qr <= nl || nr <= ql) {
return Node();
}
push(node);
int nm = (nl + nr) / 2;
Node res = get(ql, qr, node * 2, nl, nm) + get(ql, qr, node * 2 + 1, nm, nr);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
return res;
}
pair<int, int> get_kth(int ql, int qr, int val, int k, int node = 1, int nl = 0, int nr = R) {
if (qr <= nl || nr <= ql) {
return make_pair(-1, 0);
}
if (ql <= nl && nr <= qr) {
if (tree[node].mx != val) {
return make_pair(-1, 0);
}
if (tree[node].cnt_mx <= k) {
return make_pair(-1, tree[node].cnt_mx);
}
if (nl == nr - 1) {
return make_pair(nl, 0);
}
push(node);
int nm = (nl + nr) / 2;
if (tree[node * 2].mx == val && tree[node * 2].cnt_mx > k) {
pair<int, int> res = get_kth(ql, qr, val, k, node * 2, nl, nm);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
return res;
}
if (tree[node * 2].mx == val) {
k -= tree[node * 2].cnt_mx;
}
pair<int, int> res = get_kth(ql, qr, val, k, node * 2 + 1, nm, nr);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
return res;
}
push(node);
int nm = (nl + nr) / 2;
pair<int, int> res = get_kth(ql, qr, val, k, node * 2, nl, nm);
if (res.first == -1) {
k -= res.second;
pair<int, int> res2 = get_kth(ql, qr, val, k, node * 2 + 1, nm, nr);
res.first = res2.first;
res.second += res2.second;
}
tree[node] = tree[node * 2] + tree[node * 2 + 1];
return res;
}
void initialise(int n, int q, int h[]) {
for (int i = 0; i < n; ++i) {
tree[i + R].mx = h[i + 1];
tree[i + R].cnt_mx = 1;
tree[i + R].sum = h[i + 1];
}
build();
}
void cut(int l, int r, int k) {
l--;
while (k) {
Node res = get(l, r);
if ((res.mx - res.mx2) * 1LL * res.cnt_mx <= k && res.mx2 != -1) {
k -= (res.mx - res.mx2) * 1LL * res.cnt_mx;
assign_mn(l, r, res.mx2);
continue;
}
if (res.mx2 == -1 && res.mx * 1LL * res.cnt_mx <= k) {
assign_mn(l, r, 0);
break;
}
if (k % res.cnt_mx == 0) {
assign_mn(l, r, res.mx - k / res.cnt_mx);
} else {
int vl = k % res.cnt_mx;
pair<int, int> pos = get_kth(l, r, res.mx, vl);
assign_mn(l, pos.first, res.mx - k / res.cnt_mx - 1);
assign_mn(pos.first, r, res.mx - k / res.cnt_mx);
}
break;
}
}
void magic(int i, int x) {
i--;
assign_pos(i, x);
}
long long int inspect(int l, int r) {
l--;
return get(l, r).sum;
}
