#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
int a[300001];
struct seg {
int mx, cnt, smx;
long long sm;
};
struct node {
int s, e, m, lz;
seg v;
node *l, *r;
node(int _s, int _e) {
s = _s, e = _e, m = (s+e)/2;
if(s != e) {
l = new node(s, m);
r = new node(m+1, e);
v = merge(l->v, r->v);
} else {
v.sm = v.mx = a[s];
v.cnt = 1; v.smx = -1;
}
}
seg merge(seg a, seg b) {
seg ans;
ans.sm = a.sm + b.sm;
ans.mx = max(a.mx, b.mx);
if(a.mx == b.mx) {
ans.cnt = a.cnt + b.cnt;
ans.smx = max(a.smx, b.smx);
} else if(a.mx > b.mx) {
ans.cnt = a.cnt;
ans.smx = max(a.smx, b.mx);
} else {
ans.cnt = b.cnt;
ans.smx = max(a.mx, b.smx);
}
return ans;
}
void prop() {
if(s == e) return;
int mxx = max(l->v.mx, r->v.mx);
if(l->v.mx == mxx) {
l->v.sm += l->v.cnt * lz;
l->v.mx += lz;
l->lz += lz;
}
if(r->v.mx == mxx) {
r->v.sm += r->v.cnt * lz;
r->v.mx += lz;
r->lz += lz;
}
lz = 0;
}
void chmin(int x, int y, int val) {
prop();
if(val >= v.mx) return;
if(x <= s && e <= y && val > v.smx) {
lz += val-v.mx;
v.sm += (val-v.mx) * v.cnt;
v.mx = val; return;
} else if(x > m) r->chmin(x, y, val);
else if(y <= m) l->chmin(x, y, val);
else l->chmin(x, y, val), r->chmin(x, y, val);
v = merge(l->v, r->v);
}
void update(int x, int val) {
prop();
if(s == e) {
lz += val-v.mx;
v.sm += val-v.mx;
v.mx = val; return;
} else if(x > m) r->update(x, val);
else l->update(x, val);
v = merge(l->v, r->v);
}
seg query(int x, int y) {
prop();
if(x <= s && e <= y) return v;
else if(x > m) return r->query(x, y);
else if(y <= m) return l->query(x, y);
else return merge(l->query(x, y), r->query(x, y));
}
int bsta(int x, int val, int &num) {
prop();
if(s == e) {
num -= v.mx == val;
return s;
}
if(x > m) return r->bsta(x, val, num);
else if(s < x || l->v.mx > val) {
int res = l->bsta(x, val, num);
if(num <= 0) return res;
else return r->bsta(x, val, num);
} else if(l->v.mx < val) return r->bsta(x, val, num);
else if(l->v.cnt < num) {
num -= l->v.cnt;
return r->bsta(x, val, num);
} else return l->bsta(x, val, num);
}
} *root;
void initialise(int N, int Q, int h[]) {
for(int i = 1; i <= N; i++) a[i] = h[i];
root = new node(1, N);
}
void cut(int l, int r, int k) {
while(k) {
seg res = root->query(l, r);
res.smx = max(res.smx, 0);
if(res.mx == 0) break;
if((long long)(res.mx-res.smx) * res.cnt <= k) {
k -= (long long)(res.mx-res.smx) * res.cnt;
root->chmin(l, r, res.smx);
} else {
int sub = k/res.cnt, num = k % res.cnt;
if(num == 0) {
root->chmin(l, r, res.mx - sub);
}
else {
int idx = root->bsta(l, res.mx, num);
root->chmin(l, idx, res.mx - sub - 1);
root->chmin(idx+1, r, res.mx - sub);
}
break;
}
}
}
void magic(int i, int x) {
root->update(i, x);
}
long long int inspect(int l, int r) {
return root->query(l, r).sm;
}
