#include "weirdtree.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
const int maxn = 3e5 + 200, maxm = 1e4 + 200, inf = 1e9;
int n;
struct node{
ll sum = 0;
ll max1 = 0;
ll max2 = 0;
ll fr = 0;
} t[maxn * 4];
ll mv[maxn * 4];
node merge(node a, node b){
node c;
c.sum = a.sum + b.sum;
c.max1 = max(a.max1, b.max1);
if (a.max1 == b.max1){
c.fr = a.fr + b.fr;
c.max2 = max(a.max2, b.max2);
}
else{
if (a.max1 > b.max1){
c.fr = a.fr;
c.max2 = max(a.max2, b.max1);
}
else{
c.fr = b.fr;
c.max2 = max(b.max2, a.max1);
}
}
return c;
}
void push(int v, int l, int r){
if (mv[v]){
if (l != r){
if (t[v + v].max1 + mv[v + v] == t[v].max1){
mv[v + v] += mv[v];
}
if (t[v + v + 1].max1 + mv[v + v + 1] == t[v].max1){
mv[v + v + 1] += mv[v];
}
}
t[v].sum += mv[v] * t[v].fr;
t[v].max1 += mv[v];
mv[v] = 0;
}
}
void upd(int pos, ll val, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (tl == tr){
t[v].sum = val;
t[v].max1 = val;
t[v].fr = 1;
t[v].max2 = 0;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm){
upd(pos, val, v + v, tl, tm);
}
else{
upd(pos, val, v + v + 1, tm + 1, tr);
}
push(v + v, tl, tm);
push(v + v + 1, tm + 1, tr);
t[v] = merge(t[v + v], t[v + v + 1]);
}
node get(int l, int r, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (l <= tl && tr <= r){
return t[v];
}
if (l > tr || r < tl){
node cl;
cl.sum = 0;
cl.max1 = 0;
cl.max2 = 0;
cl.fr = 0;
return cl;
}
int tm = (tl + tr) / 2;
return merge(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
void updlr(int l, int r, ll x, ll mx, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (l > tr || r < tl || t[v].max1 < mx)
return;
if (l <= tl && tr <= r && t[v].max1 - x > t[v].max2 && t[v].max1 == mx){
mv[v] -= x;
push(v, tl, tr);
return;
}
if (tl == tr && t[v].max1 == mx){
mv[v] -= (x);
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
updlr(l, r, x, mx, v + v, tl, tm);
updlr(l, r, x, mx, v + v + 1, tm + 1, tr);
t[v] = merge(t[v + v], t[v + v + 1]);
}
void updlr2(int l, int r, ll x, ll &y, ll mx, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (l > tr || r < tl || t[v].max1 < mx){
return;
}
if (l <= tl && tr <= r && t[v].max1 - x - (y > 0) > t[v].max2 && (y == 0 || y >= t[v].fr) && t[v].max1 == mx){
mv[v] -= (x + (y > 0));
y = max(0ll, y - t[v].fr);
push(v, tl, tr);
// cout << t[v].sum << '\n';
// cout << mv[v + v] << " " << mv[v + v + 1] << '\n';
// cout << "kekok\n";
return;
}
if (tl == tr && t[v].max1 == mx && (y == 0 || y >= t[v].fr)){
mv[v] -= (x + (y > 0));
y = max(0ll, y - t[v].fr);
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
updlr2(l, r, x, y, mx, v + v, tl, tm);
updlr2(l, r, x, y, mx, v + v + 1, tm + 1, tr);
t[v] = merge(t[v + v], t[v + v + 1]);
}
ll gets(int l, int r, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (l <= tl && tr <= r)
return t[v].sum;
if (l > tr || r < tl)
return 0;
int tm = (tl + tr) / 2;
return gets(l, r, v + v, tl, tm) + gets(l, r, v + v + 1, tm + 1, tr);
}
void initialise(int N, int Q, int h[]) {
n = N;
for (int i = 1; i <= n; ++i){
upd(i, h[i]);
}
}
void cut(int l, int r, int k) {
while (k > 0){
node cur = get(l, r);
if (cur.max1 == 0){
break;
}
ll rz = cur.max1 - cur.max2;
if (rz * cur.fr <= k){
updlr(l, r, rz, cur.max1);
k -= rz * cur.fr;
}
else{
ll all = rz * cur.fr;
ll is = k % cur.fr;
// cout << "ok\n";
updlr2(l, r, k / cur.fr, is, cur.max1);
k = 0;
break;
}
}
}
void magic(int i, int x) {
upd(i, x);
}
long long int inspect(int l, int r) {
// Your code here.
return gets(l, r);
}
