#include <bits/stdc++.h>
#include "weirdtree.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
int n;
struct date
{
ll max1,max2,fr1,suma,lazy;
} arb[1500005];
ll need=0;
void build(int nod,int st,int dr)
{
arb[nod].fr1=dr-st+1;
arb[nod].max1=0;
arb[nod].max2=0;
arb[nod].suma=0;
arb[nod].lazy=0;
if(st==dr)
return;
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
}
date combine(date a, date b)
{
date rez={0,0,0,0,0};
rez.suma=(a.suma+b.suma);
rez.max1=max(a.max1,b.max1);
if(a.max1==b.max1)
{
rez.fr1=a.fr1+b.fr1;
rez.max2=max(a.max2,b.max2);
}
else if(a.max1>b.max1)
{
rez.fr1=a.fr1;
rez.max2=max(a.max2,b.max1);
}
else if(a.max1<b.max1)
{
rez.fr1=b.fr1;
rez.max2=max(a.max1,b.max2);
}
return rez;
}
void prop(int nod)
{
assert(arb[nod].max1>=arb[nod].max2);
int val=arb[nod].lazy;
for(int i=nod*2;i<=nod*2+1;i++)
if(arb[i].max1-val==arb[nod].max1)
{
arb[i].max1-=val;
arb[i].lazy+=val;
arb[i].suma-=val*arb[i].fr1;
assert(arb[i].max1>arb[i].max2||(arb[i].max1==0));
}
}
ll lft;
void cutupd(int nod,int st,int dr,int a,int b,ll val,int extra)
{
if(st!=dr)
prop(nod);
arb[nod].lazy=0;
int mij=(st+dr)/2;
date x=arb[nod];
ll aux=extra;
if(st>=a&&dr<=b&&arb[nod].max1==need)
{
if(extra>=x.fr1)
{
val++;
extra=0;
}
if(st==dr)
{
arb[nod].max1=max(arb[nod].max1-val,0LL);
arb[nod].suma=arb[nod].max1;
arb[nod].fr1=1;
lft=max(0LL,lft-1);
return;
}
if(x.max1-val>x.max2&&extra==0)
{
arb[nod].max1-=val;
arb[nod].lazy+=val;
arb[nod].suma-=1LL*val*arb[nod].fr1;
lft=max(0LL,lft-arb[nod].fr1);
return;
}
else if(x.max1-val==x.max2&&extra==0)
{
if(arb[nod*2].max1==x.max1)
cutupd(nod*2,st,mij,a,b,val,extra);
if(arb[nod*2+1].max1==x.max1)
cutupd(nod*2+1,mij+1,dr,a,b,val,extra);
arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
return;
}
if(arb[nod*2].max1==x.max1)
{
int put=min(extra*1LL,arb[nod*2].fr1);
cutupd(nod*2,st,mij,a,b,val,put);
if(arb[nod*2+1].max1==x.max1)
cutupd(nod*2+1,mij+1,dr,a,b,val,extra-put);
arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
return;
}
cutupd(nod*2+1,mij+1,dr,a,b,val,extra);
arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
return;
}
if(a<=mij&&arb[nod*2].max1>=need)
cutupd(nod*2,st,mij,a,b,val,lft);
if(b>mij&&arb[nod*2+1].max1>=need)
cutupd(nod*2+1,mij+1,dr,a,b,val,lft);
arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
}
void magicupd(int nod,int st,int dr,int poz,int val)
{
if(st!=dr&&arb[nod].lazy!=0)
prop(nod);
arb[nod].lazy=0;
if(st==poz&&dr==poz)
{
arb[nod].suma=val;
arb[nod].max1=val;
arb[nod].fr1=1;
arb[nod].max2=0;
arb[nod].lazy=0;
return;
}
int mij=(st+dr)/2;
if(poz<=mij)
magicupd(nod*2,st,mij,poz,val);
if(poz>mij)
magicupd(nod*2+1,mij+1,dr,poz,val);
arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
}
date query(int nod,int st,int dr,int a, int b)
{
if(st!=dr)
prop(nod);
arb[nod].lazy=0;
if(st>=a&&dr<=b)
return arb[nod];
date rez={0,0,0,0,0};
ll mij=(st+dr)/2;
if(a<=mij)
{
date x=query(nod*2,st,mij,a,b);
rez=combine(rez,x);
}
if(b>mij)
{
date x=query(nod*2+1,mij+1,dr,a,b);
rez=combine(rez,x);
}
return rez;
}
void initialise(int N, int Q, int h[]) {
n=N;
build(1,1,n);
for(int i=1;i<=n;i++)
magicupd(1,1,n,i,h[i]);
}
void cut(int l, int r, int k) {
while(k>0)
{
date x=query(1,1,n,l,r);
ll fr1=x.fr1;
ll max1=x.max1;
need=x.max1;
if(max1==0)
break;
ll max2=x.max2;
if((max1-max2)*fr1<=k)
{
cutupd(1,1,n,l,r,max1-max2,0);
k-=(max1-max2)*fr1;
continue;
}
ll val=k/fr1;
ll extra=k%fr1;
lft=extra;
cutupd(1,1,n,l,r,val,extra);
k=0;
break;
}
}
void magic(int i, int x) {
magicupd(1,1,n,i,x);
}
long long int inspect(int l, int r) {
return query(1,1,n,l,r).suma;
}
