#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;
int n;
struct Node{
int mx, smx, cnt;
Node(){}
Node(int x):mx(x), smx(0), cnt(1) {}
Node(int _mx, int _smx, int _cnt): mx(_mx), smx(_smx), cnt(_cnt){}
Node operator + (const Node &N) const{
Node ret;
if (mx > N.mx) ret.mx = mx, ret.smx = max(N.mx, smx), ret.cnt = cnt;
else if (mx < N.mx) ret.mx = N.mx, ret.smx = max(mx, N.smx), ret.cnt = N.cnt;
else ret.mx = mx, ret.smx = max(smx, N.smx), ret.cnt = cnt + N.cnt;
return ret;
}
};
struct Seg{
Node tree[1201200];
ll tree2[1201200];
int lazy[1201200];
void init(int i, int l, int r, int a[]){
lazy[i] = INF;
if (l==r){
tree[i] = Node(a[l]);
tree2[i] = a[l];
return;
}
int m = (l+r)>>1;
init(i<<1, l, m, a); init(i<<1|1, m+1, r, a);
tree[i] = tree[i<<1] + tree[i<<1|1];
tree2[i] = tree2[i<<1] + tree2[i<<1|1];
}
void propagate(int i, int l, int r){
if (lazy[i]==INF) return;
int d = tree[i].mx - min(tree[i].mx, lazy[i]);
tree2[i] -= (ll)d * tree[i].cnt;
tree[i].mx = min(tree[i].mx, lazy[i]);
assert(tree[i].mx > tree[i].smx || tree[i].mx==0);
if (l!=r){
lazy[i<<1] = min(lazy[i<<1], lazy[i]);
lazy[i<<1|1] = min(lazy[i<<1|1], lazy[i]);
}
lazy[i] = INF;
}
void updateM(int i, int l, int r, int s, int e, int x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e && (x > tree[i].smx || (x==0 && tree[i].smx==0))){
lazy[i] = x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
updateM(i<<1, l, m, s, e, x); updateM(i<<1|1, m+1, r, s, e, x);
tree[i] = tree[i<<1] + tree[i<<1|1];
tree2[i] = tree2[i<<1] + tree2[i<<1|1];
}
void updateV(int i, int l, int r, int p, int x){
propagate(i, l, r);
if (r<p || p<l) return;
if (l==r){
tree[i] = Node(x);
tree2[i] = x;
return;
}
int m = (l+r)>>1;
updateV(i<<1, l, m, p, x); updateV(i<<1|1, m+1, r, p, x);
tree[i] = tree[i<<1] + tree[i<<1|1];
tree2[i] = tree2[i<<1] + tree2[i<<1|1];
}
int prefix(int i, int l, int r, int s, int val, int cnt){
// printf(" call %d %d %d %d %d %d\n", i, l, r, s, val, cnt);
propagate(i, l, r);
if (r<s) return 0;
if (s<=l){
if (tree[i].mx < val) return 0;
if (tree[i].mx==val && tree[i].cnt < cnt) return -tree[i].cnt;
if (l==r){
if (tree[i].mx == val) return l;
else return 0;
}
}
int m = (l+r)>>1;
int ret1 = prefix(i<<1, l, m, s, val, cnt);
if (ret1 > 0) return ret1;
cnt += ret1;
int ret2 = prefix(i<<1|1, m+1, r, s, val, cnt);
if (ret2 > 0) return ret2;
return ret1 + ret2;
}
Node query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if (r<s || e<l) return Node(0, 0, 0);
if (s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
}
ll sum(int i, int l, int r, int s, int e){
propagate(i, l, r);
if (r<s || e<l) return 0;
if (s<=l && r<=e) return tree2[i];
int m = (l+r)>>1;
return sum(i<<1, l, m, s, e) + sum(i<<1|1, m+1, r, s, e);
}
}tree;
void initialise(int N, int Q, int h[]) {
n = N;
tree.init(1, 1, n, h);
}
void cut(int l, int r, int k) {
while(k > 0){
auto N = tree.query(1, 1, n, l, r);
// printf("ok %d %d cnt = %d / k = %d\n", N.mx, N.smx, N.cnt, k);
if (k >= (ll)N.cnt * (N.mx - N.smx)){
k -= (ll)N.cnt * (N.mx - N.smx);
tree.updateM(1, 1, n, l, r, N.smx);
if (N.smx==0) return;
}
else{
int quo = k / N.cnt, rem = k % N.cnt;
int idx = l-1;
if (rem > 0) idx = tree.prefix(1, 1, n, l, N.mx, rem);
// printf(" okok idx = %d\n", idx);
if (l<=idx) tree.updateM(1, 1, n, l, idx, N.mx-quo-1);
if (idx+1<=r) tree.updateM(1, 1, n, idx+1, r, N.mx-quo);
return;
}
}
}
void magic(int i, int x) {
tree.updateV(1, 1, n, i, x);
}
long long int inspect(int l, int r) {
return tree.sum(1, 1, n, l, r);
}
