#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll height[1005];
int nums;
struct node{
int s, e, m; pair<ll, int> val; ll sum;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1, val = {0, -s}, sum = 0;
if (s != e){
l = new node(s, m);
r = new node(m + 1, e);
}
}
void update(int p, ll v){
if (s == e){
val.first = v;
sum = v;
return;
}
else if (p <= m) l->update(p, v);
else r->update(p, v);
val = max(l->val, r->val);
sum = l->sum + r->sum;
}
pair<ll, int> qmax(int x, int y){
if (x == s && y == e) return val;
else if (y <= m) return l->qmax(x, y);
else if (x > m) return r->qmax(x, y);
else return max(l->qmax(x, m), r->qmax(m + 1, y));
}
ll qsum(int x, int y){
if (x == s && y == e) return sum;
else if (y <= m) return l->qsum(x, y);
else if (x > m) return r->qsum(x, y);
else return l->qsum(x, m)+ r->qsum(m + 1, y);
}
}*root;
void initialise(int N, int Q, int h[]) {
nums = N;
if (nums <= 1000){
for (int i = 1; i <= N; i++) height[i] = h[i];
}
else{
root = new node(1, N);
for (int i = 1; i <= N; i++) root->update(i, h[i]);
}
}
void cut(int l, int r, int k) {
if (nums <= 1000){
ll lh = 0, rh = 1e9 + 5, ans = 0;
while (lh <= rh){
ll mh = (lh + rh) >> 1, sum = 0;
for (int i = l; i <= r; i++)
if (height[i] > mh)
sum += height[i] - mh;
if (sum >= k){
ans = mh;
lh = mh + 1;
}
else rh = mh - 1;
}
ll sum = 0;
for (int i = l; i <= r; i++)
if (height[i] > ans)
sum += height[i] - ans;
if (sum >= k){
ll rem = sum - k;
for (int i = r; i >= l; i--)
if (height[i] > ans){
if (rem > 0){
height[i] = ans + 1;
rem--;
}
else height[i] = ans;
}
}
else{
for (int i = l; i <= r; i++) height[i] = 0;
}
}
else{
for (int i = 0; i < k; i++){
auto res = root->qmax(l, r);
if (res.first == 0) break;
root->update(-res.second, res.first - 1);
}
}
}
void magic(int i, int x) {
if (nums <= 1000) height[i] = x;
else root->update(i, x);
}
ll inspect(int l, int r) {
if (nums <= 1000){
ll sum = 0;
for (int i = l; i <= r; i++) sum += height[i];
return sum;
}
return root->qsum(l, r);
}
