#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 80000 + 1;
struct node
{
int mx=-1,id;
ll su=0;
};
node seg[M*2];
int n;
node merge(node a,node b)
{
a.su=b.su=a.su+b.su;
if (a.mx<b.mx)
return b;
return a;
}
void modify(int p,int x,int v=0,int s=1,int e=n+1)
{
if (s+1==e)
{
seg[v].mx=seg[v].su=x,seg[v].id=p;
return;
}
int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
if (p<mid)
modify(p,x,lc,s,mid);
else
modify(p,x,rc,mid,e);
seg[v]=merge(seg[lc],seg[rc]);
}
node get(int l,int r,int v=0,int s=1,int e=n+1)
{
if (l>=e or r<=s)
return seg[M*2-1];
if (l<=s && e<=r)
return seg[v];
int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
return merge(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}
void initialise(int N, int Q, int h[])
{
n=N;
for (int i=1;i<=n;i++)
modify(i,h[i]);
}
void cut(int l, int r, int k)
{
node a=get(l,r+1);
modify(a.id,a.mx-1);
}
void magic(int i, int x) {
modify(i,x);
}
long long int inspect(int l, int r) {
return get(l,r+1).su;
}
