#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1000 + 1;
int n,a[M];
void initialise(int N, int Q, int h[])
{
n=N;
for (int i=1;i<=n;i++)
a[i]=h[i];
}
void cut(int l, int r, int k)
{
map<int,int,greater<int>> se;
ll su=0,cnt=0,v;
se[0]=0;
for (int i=l;i<=r;i++)
su+=a[i],se[a[i]]++;
if (su<=k)
{
for (int i=l;i<=r;i++) a[i]=0;
return;
}
su=0;
for (auto [x,c]:se)
{
if (su-cnt*x>=k)
{
v=x;
break;
}
else
su+=x*c,cnt+=c;
}
set<int,greater<int>> id;
for (int i=l;i<=r;i++)
if (a[i]>v)
id.insert(i);
ll s=-1,e=su/cnt;
while (s+1<e)
{
ll mid=(s+e)/2;
if (su-mid*cnt>=k)
s=mid;
else
e=mid;
}
for (int i:id)
a[i]=s;
cnt=su-cnt*s-k;
for (int i:id)
if (!cnt) break;
else a[i]++,cnt--;
}
void magic(int i, int x) {
a[i]=x;
}
long long int inspect(int l, int r) {
ll ans=0;
for (int i=l;i<=r;ans+=a[i],i++);
return ans;
}
