#pragma GCC optimize("O2,unroll-loops")
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int N = 3e5 + 7;
const int inf = 1e9 + 7;
struct Node{
int maxcnt , max1 , max2 , chmin;
long long sum;
Node():maxcnt(0),max1(0),max2(0),sum(0),chmin(inf){}
} dumb;
Node merge(Node a , Node b){
Node c;
c.max1 = max(a.max1 , b.max1);
if(c.max1 == a.max1)c.maxcnt += a.maxcnt;
if(c.max1 == b.max1)c.maxcnt += b.maxcnt;
if(c.max1 != a.max1)c.max2 = max(c.max2 , a.max1);
if(c.max1 != a.max2)c.max2 = max(c.max2 , a.max2);
if(c.max1 != b.max1)c.max2 = max(c.max2 , b.max1);
if(c.max1 != b.max2)c.max2 = max(c.max2 , b.max2);
c.sum = a.sum + b.sum;
return c;
}
vector<Node> tree(4 * N);
void push(int ind , int l , int r){
if(tree[ind].chmin != inf){
// cout << "push0 : " << ind << " " << l << " " << r << endl;
// cout << "max1 : " << tree[ind].max1 << endl;
// cout << "max2 : " << tree[ind].max2 << endl;
// cout << "maxcnt : " << tree[ind].maxcnt << endl;
// cout << "chmin : " << tree[ind].chmin << endl;
if(tree[ind].chmin <= tree[ind].max1 and tree[ind].max2 < tree[ind].chmin){
tree[ind].sum -= 1LL * tree[ind].maxcnt * (tree[ind].max1 - tree[ind].chmin);
tree[ind].max1 = tree[ind].chmin;
if(l != r){
tree[ind*2].chmin = min(tree[ind*2].chmin , tree[ind].chmin);
tree[ind*2+1].chmin = min(tree[ind*2+1].chmin , tree[ind].chmin);
}
}
else if(tree[ind].chmin <= tree[ind].max2){
assert(l != r);
int mid = (l + r) / 2;
tree[ind*2].chmin = min(tree[ind*2].chmin , tree[ind].chmin);
push(ind*2 , l , mid);
tree[ind*2+1].chmin = min(tree[ind*2+1].chmin , tree[ind].chmin);
push(ind*2+1 , mid+1 , r);
tree[ind] = merge(tree[ind*2] , tree[ind*2+1]);
}
tree[ind].chmin = inf;
// cout << "push1" << endl;
}
}
Node query(int ql , int qr , int ind=1 , int l=0 , int r=N){
push(ind,l,r);
// cout << "SUM = " << l << " " << r << " : " << tree[ind].sum << endl;
if(l >= ql and r <= qr){
// cout << " GOT IT : " << l << " " << r << " " << tree[ind].sum << endl;
return tree[ind];
}
else if(l > qr or r < ql){
return dumb;
}
int mid = (l + r) / 2;
return merge(query(ql,qr,ind*2,l,mid) , query(ql,qr,ind*2+1,mid+1,r));
}
void update_set(int qp , int qv , int ind=1 , int l=0 , int r=N){
push(ind,l,r);
if(l == r){
push(ind,l,r);
tree[ind].maxcnt = 1;
tree[ind].max1 = qv;
tree[ind].sum = qv;
tree[ind].max2 = -inf;
tree[ind].chmin = inf;
// cout << l << " " << r << " | sum : " << tree[ind].sum << endl;
return;
}
int mid = (l + r) / 2;
if(qp <= mid)update_set(qp , qv , ind*2 , l , mid);
else update_set(qp , qv , ind*2+1 , mid+1 , r);
push(ind*2 , l , mid);
push(ind*2+1 , mid+1 , r);
tree[ind] = merge(tree[ind*2] , tree[ind*2+1]);
// cout << l << " " << r << " | sum : " << tree[ind].sum << endl;
}
void update_chmin(int ql , int qr , int qv , int ind=1 , int l=0 , int r=N){
push(ind,l,r);
if(l >= ql and r <= qr){
// cout << "APPLIED : " << l << " " << r << " " << qv << endl;
tree[ind].chmin = min(tree[ind].chmin , qv);
push(ind,l,r);
return;
}
else if(l > qr or r < ql)return;
int mid = (l + r) / 2;
update_chmin(ql , qr , qv , ind*2 , l , mid);
update_chmin(ql , qr , qv , ind*2+1 , mid+1 , r);
push(ind*2 , l , mid);
push(ind*2+1 , mid+1 , r);
tree[ind] = merge(tree[ind*2] , tree[ind*2+1]);
}
int ANSWER = -1;
int sayac = 0;
int getkth(int ql , int qr , int qv , int qcnt , int ind=1 , int l=0 , int r=N){
sayac++;
push(ind,l,r);
if(qcnt <= 0)return 0;
else if(tree[ind].max1 < qv)return 0;
// cout << "getkth : " << l << " " << r << " " << qcnt << endl;
if(l == r){
if(tree[ind].max1 == qv and l >= ql and r <= qr){
if(qcnt == 1){
ANSWER = l;
}
return 1;
}
else return 0;
}
int mid = (l + r) / 2;
if(l >= ql and r <= qr){
// cout << l << " " << r << " " << tree[ind].max1 << " == " << qv << endl;
if(tree[ind].max1 == qv and qcnt > tree[ind].maxcnt){
return tree[ind].maxcnt;
}
else{
int A = getkth(ql , qr , qv , qcnt , ind*2 , l , mid);
int B = getkth(ql , qr , qv , qcnt - A , ind*2+1 , mid+1 , r);
return A + B;
}
}
else if(l > qr or r < ql)return 0;
int A = getkth(ql , qr , qv , qcnt , ind*2 , l , mid);
int B = getkth(ql , qr , qv , qcnt - A , ind*2+1 , mid+1 , r);
return A + B;
}
void initialise(int N, int Q, int h[]) {
// cout << "flag0" << endl;
for(int i = 1;i<=N;i++){
update_set(i , h[i]);
}
// cout << "flag1" << endl;
// cout << "DONEEE" << endl;
}
void cut(int l, int r, int k) {
// cout << "cut : " << l << " " << r << " " << k << endl;
// cout << "BEFORE : ";for(int i = 1;i<=5;i++)cout << query(i,i).max1 << " ";cout << endl;
// cout << "flag2" << endl;
while(k){
// cout << "NEWCYCLE!!!" << endl;
// cout << "K : " << k << endl;
Node tmp = query(l,r);
if(tmp.max1 == 0)break;
// cout << "max1 : " << tmp.max1 << endl;
// cout << "max2 : " << tmp.max2 << endl;
// cout << "maxcnt : " << tmp.maxcnt << endl;
int steps = min(tmp.max1 - tmp.max2 , k / tmp.maxcnt);
// cout << "steps : " << steps << endl;
// cout << "flag2.1 : " << steps << endl;
if(steps){
// cout << "shave off" << endl;
update_chmin(l , r , tmp.max1 - steps);
k -= steps * tmp.maxcnt;
}
// cout << "K : " << k << endl;
// cout << "flag2.3" << endl;
if(steps != tmp.max1 - tmp.max2 and k % tmp.maxcnt){
// int L = l , R = r;
// while(L < R){
// int MID = (L + R) / 2;
// auto bro = query(l,MID);
// // cout << "MID " << MID << " : " << bro.max1 << " , " << bro.maxcnt << endl;
// if(bro.max1 != tmp.max1-steps or bro.maxcnt < k % tmp.maxcnt){
// // cout << "FLAG0" << endl;
// L = MID+1;
// }
// else {
// // cout << "FLAG1" << endl;
// R = MID;
// }
// }
ANSWER = -1;
sayac = 0;
// cout << "l r : " << l << " " << r << endl;
// cout << "target : " << tmp.max1 - steps << endl;
// cout << "realmax : " << query(l,r).max1 << endl;
getkth(l , r , tmp.max1 - steps , k % tmp.maxcnt);
// cout << "sayac : " << sayac << endl;
// ANSWER = L;
// cout << "L : " << L << endl;
// cout << "ANSWER : " << ANSWER << endl;
// while(L != ANSWER){}
// assert(L == ANSWER);
update_chmin(l , ANSWER , tmp.max1 - steps - 1);
k -= k % tmp.maxcnt;
}
// cout << "K : " << k << endl;
// cout << "flag2.4" << endl;
}
// cout << "flag3" << endl;
// cout << "AFTER : ";for(int i = 1;i<=5;i++)cout << query(i,i).max1 << " ";cout << endl;
}
void magic(int i, int x) {
// cout << "magic : " << i << " " << x << endl;
update_set(i , x);
// cout << "AFTER : ";for(int i = 1;i<=5;i++)cout << query(i,i).max1 << " ";cout << endl;
}
long long int inspect(int l, int r) {
// cout << "bfrquery : ";for(int i = 1;i<=5;i++)cout << query(i,i).max1 << " ";cout << endl;
return query(l,r).sum;
}
// int main() {
// int N, Q;
// cin >> N >> Q;
// int h[N + 1];
// for (int i = 1; i <= N; ++i) cin >> h[i];
// initialise(N, Q, h);
// int sayac = 0;
// for (int i = 1; i <= Q; ++i) {
// int t;
// cin >> t;
// if (t == 1) {
// int l, r, k;
// cin >> l >> r >> k;
// cut(l, r, k);
// } else if (t == 2) {
// int i, x;
// cin >> i >> x;
// magic(i, x);
// } else {
// int l, r;
// cin >> l >> r;
// cout << inspect(l, r) << '\n';
// cout << "sayac : " << sayac++ << '\n';
// }
// }
// return 0;
// }
