#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
using ll = long long;
//#define int long long
struct RMQ {
vector<ll>t,a;
int size=1, n;
int merge(int i, int j) {
if (a[i]>=a[j]) return i;
else return j;
}
void update(int i, int l, int r, int p) {
if (r-l==1) return;
if (r<=p || l>p) return;
int mid=(r+l)>>1;
update(2*i+1,l,mid,p);
update(2*i+2,mid,r,p);
t[i]=merge(t[2*i+1],t[2*i+2]);
}
void update(int i, int l, int r) {
if (r-l==1) return;
int mid=(r+l)>>1;
update(2*i+1,l,mid);
update(2*i+2,mid,r);
t[i]=merge(t[2*i+1],t[2*i+2]);
}
RMQ(vector<ll>&v) {
a=v;
n=a.size();
a.push_back(-1e9);
while (size<n) size<<=1;
t.assign(2*size-1,n);
forn(i,n) t[size-1+i]=i;
update(0,0,size);
}
int query(int i, int l, int r, int lx, int rx) {
if (l>=rx || r<=lx) return n;
if (l>=lx && r<=rx) return t[i];
int mid=(l+r)>>1;
int L=query(2*i+1,l,mid,lx,rx);
int R=query(2*i+2,mid,r,lx,rx);
return merge(L,R);
}
int query(int l, int r) {
return query(0,0,size,l,r);
}
void set(int i, int x) {
a[i]=x;
update(0,0,size,i);
}
};
struct aint {
vector<ll>t,a;
int size=1, n;
ll merge(ll i, ll j) {
return i+j;
}
void update(int i, int l, int r, int p) {
if (r-l==1) return;
if (r<=p || l>p) return;
int mid=(r+l)>>1;
update(2*i+1,l,mid,p);
update(2*i+2,mid,r,p);
t[i]=merge(t[2*i+1],t[2*i+2]);
}
void update(int i, int l, int r) {
if (r-l==1) return;
int mid=(r+l)>>1;
update(2*i+1,l,mid);
update(2*i+2,mid,r);
t[i]=merge(t[2*i+1],t[2*i+2]);
}
aint(vector<ll>&v) {
a=v;
n=a.size();
while (size<n) size<<=1;
t.assign(2*size-1,0);
forn(i,n) t[size-1+i]=a[i];
update(0,0,size);
}
ll query(int i, int l, int r, int lx, int rx) {
if (l>=rx || r<=lx) return 0;
if (l>=lx && r<=rx) return t[i];
int mid=(l+r)>>1;
ll L=query(2*i+1,l,mid,lx,rx);
ll R=query(2*i+2,mid,r,lx,rx);
return merge(L,R);
}
ll query(int l, int r) {
return query(0,0,size,l,r);
}
void set(int i, int x) {
t[size-1+i]=x;
update(0,0,size,i);
}
};
vector<ll> a;
int n;
aint st(a);
RMQ rmq(a);
ll sum=0;
void initialise(int N, int Q, int*v) {
n=N;
forn(i,n) a.push_back(v[i+1]);
st=aint(a);
rmq=RMQ(a);
forn(i,n) sum+=a[i];
}
ll f(int x,int L, int R) {
ll r=0;
for(int i=L-1; i<R; ++i) if (a[i]>x) r+=a[i]-x;
return r;
}
void cut(int l, int r, int k) {
if (l==1 && r==n && n>1000) {
sum-=k;
return;
}
//cout<<"cut "<<l<<' '<<r<<' '<<k<<'\n';
if (k==1) {
forn(q,k) {
int i=rmq.query(l-1,r);
if (!a[i]) break;
a[i]--;
rmq.set(i,a[i]);
st.set(i,a[i]);
}
} else {
int L=l, R=r;
ll S=st.query(L-1,R);
if (S<=k) {
for (int i=L-1; i<R; ++i) a[i]=0;
for (int i=L-1; i<R; ++i) st.set(i,0);
for (int i=L-1; i<R; ++i) rmq.set(i,0);
return;
}
int l=1, r=1e9;
while (l<r) {
int mid=(l+r)>>1;
ll x=f(mid,L,R);
if (x>=k) l=mid+1;
else r=mid;
}
ll s=0;
for (int i=L-1; i<R; ++i) {
if (a[i]>r) {
s+=a[i]-r;
a[i]=r;
st.set(i,r);
rmq.set(i,r);
}
}
k-=s;
//cout<<r<<' '<<s<<' '<<k<<'\n';
//for (auto x:a) cout<<x<<' '; cout<<'\n';
forn(q,k) {
int i=rmq.query(L-1,R);
if (!a[i]) break;
a[i]--;
rmq.set(i,a[i]);
st.set(i,a[i]);
}
//for (auto x:a) cout<<x<<' '; cout<<'\n';
}
}
void magic(int i, int x) {
--i;
sum=sum-a[i]+x;
a[i]=x;
rmq.set(i,x);
st.set(i,x);
}
ll inspect(int l, int r) {
if (l==1 && r==n && n>1000) {
return sum;
}
ll ans=st.query(l-1,r);
return ans;
}
