#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
int h[300001];
struct Beats
{
int max1,max2,cntmax;
long long sum;
} aint[1200001];
void combina(int nod)
{
//suma
aint[nod].sum=aint[2*nod].sum+aint[2*nod+1].sum;
//maxim
if(aint[2*nod].max1==aint[2*nod+1].max1)
{
aint[nod].max1=aint[2*nod].max1;
aint[nod].cntmax=aint[2*nod].cntmax+aint[2*nod+1].cntmax;
aint[nod].max2=max(aint[2*nod].max2,aint[2*nod+1].max2);
}
else
{
if(aint[2*nod].max1>aint[2*nod+1].max1)
{
aint[nod].max1=aint[2*nod].max1;
aint[nod].cntmax=aint[2*nod].cntmax;
aint[nod].max2=max(aint[2*nod].max2,aint[2*nod+1].max1);
}
else
{
aint[nod].max1=aint[2*nod+1].max1;
aint[nod].cntmax=aint[2*nod+1].cntmax;
aint[nod].max2=max(aint[2*nod].max1,aint[2*nod+1].max2);
}
}
}
void pushmin(int nod,int val)
{
if(val>=aint[nod].max1)
return;
aint[nod].sum-=1LL*aint[nod].cntmax*aint[nod].max1;
aint[nod].max1=val;
aint[nod].sum+=1LL*aint[nod].cntmax*aint[nod].max1;
}
void pushdown(int nod)
{
pushmin(2*nod,aint[nod].max1);
pushmin(2*nod+1,aint[nod].max1);
}
void build(int nod,int st,int dr)
{
if(st==dr)
{
aint[nod].max1=aint[nod].sum=h[st];
aint[nod].max2=-1e9;
aint[nod].cntmax=1;
return;
}
int mid=(st+dr)/2;
build(2*nod,st,mid);
build(2*nod+1,mid+1,dr);
combina(nod);
}
long long suma(int nod,int st,int dr,int a,int b)
{
if(b<st||dr<a)
return 0;
if(a<=st&&dr<=b)
return aint[nod].sum;
pushdown(nod);
int mid=(st+dr)/2;
return suma(2*nod,st,mid,a,b)+suma(2*nod+1,mid+1,dr,a,b);
}
void WaverlyPlace(int nod,int st,int dr,int poz,int val)
{
if(poz<st||dr<poz)
return;
if(st==poz&&poz==dr)
{
aint[nod].max1=aint[nod].sum=val;
return;
}
pushdown(nod);
int mid=(st+dr)/2;
WaverlyPlace(2*nod,st,mid,poz,val);
WaverlyPlace(2*nod+1,mid+1,dr,poz,val);
combina(nod);
}
int x,vf,y;
void gimmeMax(int nod,int st,int dr,int a,int b)
{
if(b<st||dr<a)
return;
if(a<=st&&dr<=b)
{
if(aint[nod].max1>x)
{
y=x;
x=aint[nod].max1;
vf=aint[nod].cntmax;
}
else if(aint[nod].max1==x)
vf+=aint[nod].cntmax;
else if(aint[nod].max1>y)
y=aint[nod].max1;
if(aint[nod].max2>y)
y=aint[nod].max2;
return;
}
pushdown(nod);
int mid=(st+dr)/2;
gimmeMax(2*nod,st,mid,a,b);
gimmeMax(2*nod+1,mid+1,dr,a,b);
}
void updmin(int nod,int st,int dr,int a,int b,int val)
{
if(b<st||dr<a||aint[nod].max1<val)
return;
if(a<=st&&dr<=b&&aint[nod].max2<val)
{
pushmin(nod,val);
return;
}
pushdown(nod);
int mid=(st+dr)/2;
updmin(2*nod,st,mid,a,b,val);
updmin(2*nod+1,mid+1,dr,a,b,val);
combina(nod);
}
int updminpart(int nod,int st,int dr,int a,int b,int val,int cate)
{
if(b<st||dr<a||aint[nod].max1<=val||cate<=0)
return 0;
if(a<=st&&dr<=b&&aint[nod].max2<val&&aint[nod].cntmax<=cate)
{
pushmin(nod,val);
return aint[nod].cntmax;
}
pushdown(nod);
int mid=(st+dr)/2;
int x=updminpart(2*nod,st,mid,a,b,val,cate);
int y=updminpart(2*nod+1,mid+1,dr,a,b,val,cate-x);
combina(nod);
return x+y;
}
int n,q;
void initialise ( int N, int Q, int H [])
{
n=N;
q=Q;
for(int i=1; i<=n; i++)
h[i]=H[i];
build(1,1,n);
}
void cut ( int l, int r, int k )
{
while(k)
{
vf=-1;
x=y=-1e9;
gimmeMax(1,1,n,l,r);
y=max(y,0);
if(x==0&&y==0)
break;
//cout<<x<<" "<<y<<" "<<vf<<'\n';
if(k>=1LL*(x-y)*vf)
{
k-=1LL*(x-y)*vf;
updmin(1,1,n,l,r,y);
}
else
{
int y=x-k/vf;
if(y!=x)
updmin(1,1,n,l,r,y);
assert(updminpart(1,1,n,l,r,y-1,k%vf)==k%vf);
k=0;
}
}
}
void magic ( int i, int x )
{
WaverlyPlace(1,1,n,i,x);
}
long long int inspect ( int l, int r )
{
//for(int i=1;i<=n;i++)
//cout<<suma(1,1,n,i,i)<<" ";
//cout<<'\n';
return suma(1,1,n,l,r);
}
