#include "weirdtree.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 3e5 + 5;
struct Node{
int mx1, mx2, cnt1;
ll sum;
Node(){
sum = -1;
}
};
int n, q, a[lim], lazy[lim << 2];
Node st[lim << 2];
Node merge(Node a, Node b){
if(a.sum == -1){
return b;
}
if(b.sum == -1){
return a;
}
Node c;
c.mx1 = max(a.mx1, b.mx1);
c.mx2 = a.mx1 != b.mx1 ? max(max(a.mx2, b.mx2), min(a.mx1, b.mx1)) : max(a.mx2, b.mx2);
c.cnt1 = a.mx1 == b.mx1 ? a.cnt1 + b.cnt1 : (a.mx1 > b.mx1 ? a.cnt1 : b.cnt1);
c.sum = a.sum + b.sum;
return c;
}
void build(int id, int l, int r){
if(l == r){
st[id].mx1 = st[id].sum = a[l];
st[id].mx2 = 0;
st[id].cnt1 = 1;
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
void initialise(int _n, int _q, int _a[]){
for(int i = n = _n; i > 0; i--){
a[i] = _a[i];
}
q = _q;
memset(lazy, -1, sizeof(lazy));
build(1, 1, n);
}
void propagate(int id, int x){
if(st[id].mx1 > x){
st[id].sum -= ll(st[id].cnt1) * (st[id].mx1 - x);
st[id].mx1 = lazy[id] = x;
}
}
void push_down(int id){
if(lazy[id] != -1){
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = -1;
}
}
void modify(int id, int l, int r, int p, int x){
if(l == r){
st[id].mx1 = st[id].sum = x;
return;
}
int m = (l + r) >> 1;
push_down(id);
if(m < p){
modify(id << 1 | 1, m + 1, r, p, x);
}
else{
modify(id << 1, l, m, p, x);
}
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
Node get(int id, int l, int r, int u, int v){
if(l > v || r < u){
return Node();
}
if(u <= l && v >= r){
return st[id];
}
int m = (l + r) >> 1;
push_down(id);
return merge(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
void apply(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
if(st[id].mx1 == 0 || st[id].mx1 != st[id].mx2){
return;
}
}
int m = (l + r) >> 1;
push_down(id);
apply(id << 1, l, m, u, v, x);
apply(id << 1 | 1, m + 1, r, u, v, x);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
void walk(int id, int l, int r, int u, int v, int need_mx1, int& k){
if(l > v || r < u || k == 0 || st[id].mx1 < need_mx1){
return;
}
if(u <= l && v >= r && st[id].mx1 == need_mx1 && st[id].cnt1 <= k){
propagate(id, need_mx1 - 1);
k -= st[id].cnt1;
return;
}
int m = (l + r) >> 1;
push_down(id);
walk(id << 1, l, m, u, v, need_mx1, k);
walk(id << 1 | 1, m + 1, r, u, v, need_mx1, k);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
void cut(int l, int r, int k){
int need_mx1;
while(k > 0){
Node cur = get(1, 1, n, l, r);
if(cur.mx1 == 0){
k = 0;
break;
}
ll need = ll(cur.cnt1) * (cur.mx1 - cur.mx2);
if(need <= k){
k -= need;
apply(1, 1, n, l, r, cur.mx2);
}
else{
apply(1, 1, n, l, r, need_mx1 = cur.mx1 - k / cur.cnt1);
k %= cur.cnt1;
break;
}
}
if(k > 0){
walk(1, 1, n, l, r, need_mx1, k);
}
}
void magic(int i, int x){
modify(1, 1, n, i, x);
}
ll inspect(int l, int r){
return get(1, 1, n, l, r).sum;
}
