#include <bits/stdc++.h>
#include <weirdtree.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 8e4 + 25;
struct SegmentTree {
int arr[MAXN]; pair <int, int> tree[2 * MAXN];
ll sum[2 * MAXN];
void build (int l, int r, int node) {
if (l == r) {
tree[node] = {arr[l], -l};
sum[node] = arr[l];
} else {
build(l, mid, tl); build(mid + 1, r, tr);
tree[node] = max(tree[tl], tree[tr]);
sum[node] = sum[tl] + sum[tr];
}
}
void update (int l, int r, int a, int b, int node) {
if (l > a || r < a) return;
if (l == r) {
tree[node] = {b, -l};
sum[node] = b;
return;
}
update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
tree[node] = max(tree[tl], tree[tr]);
sum[node] = sum[tl] + sum[tr];
}
pair <int, int> get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return {-1, 0};
if (l >= a && r <= b) return tree[node];
return max(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
}
ll getsum (int l, int r, int a, int b, int node) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return sum[node];
return getsum(l, mid, a, b, tl) + getsum(mid + 1, r, a, b, tr);
}
} cur;
int n;
void initialise (int N, int q, int h[]) {
n = N;
for (int i = 1; i <= n; i++) cur.arr[i] = h[i];
cur.build(1, n, 1);
}
void cut (int l, int r, int z) {
auto x = cur.get(1, n, l, r, 1);
if (x.first == 0) return;
x.second *= -1;
cur.update(1, n, x.second, x.first - 1, 1);
}
void magic (int i, int x) {
cur.update(1, n, i, x, 1);
}
long long int inspect (int l, int r) {
return cur.getsum(1, n, l, r, 1);
}
