#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
using lli = long long;
struct node {
int mx, idx;
lli sum;
node (int x = 0, int i = 0, lli s = 0) : mx {x}, idx {i}, sum {s} { }
node operator+(node other) {
if (mx > other.mx) return node(mx, idx, sum + other.sum);
if (mx < other.mx) return node(other.mx, other.idx, sum + other.sum);
return node(mx, min(idx, other.idx), sum + other.sum);
}
};
const int MAXN = 3e5 + 10;
int n;
int xs[MAXN];
node seg[4*MAXN];
node query(int pos, int ini, int fim, int l, int r) {
if (l <= ini && fim <= r) return seg[pos];
if (r < ini || fim < l) return node();
int m = (ini + fim)/2;
return query(2*pos, ini, m, l, r) + query(2*pos + 1, m + 1, fim, l, r);
}
void update(int pos, int ini, int fim, int idx, int x, bool b) {
if (ini == fim) {
if (b) { seg[pos].mx = x; seg[pos].sum = x; }
else if (seg[pos].mx > 0) { seg[pos].mx += x; seg[pos].sum += x; }
return;
}
int m = (ini + fim)/2;
if (idx <= m) update(2*pos, ini, m, idx, x, b);
else update(2*pos + 1, m + 1, fim, idx, x, b);
seg[pos] = seg[2*pos] + seg[2*pos + 1];
}
void build(int pos, int ini, int fim) {
if (ini == fim) {
seg[pos] = node(xs[ini], ini, xs[ini]);
return;
}
int m = (ini + fim)/2;
build(2*pos, ini, m);
build(2*pos + 1, m + 1, fim);
seg[pos] = seg[2*pos] + seg[2*pos + 1];
}
void initialise(int sz, int q, int hs[]) {
for (int i = 1; i <= sz; ++i)
xs[i] = hs[i];
build(1, 1, sz);
n = sz;
}
void cut(int l, int r, int k) {
for (int j = 0; j < k; ++j) {
int i = query(1, 1, n, l, r).idx;
update(1, 1, n, i, -1, false);
}
}
void magic(int i, int x) {
update(1, 1, n, i, x, true);
}
lli inspect(int l, int r) {
return query(1, 1, n, l, r).sum;
}
