#include <bits/stdc++.h>
//#include "weirdtree.h"
#define il inline
using namespace std;
/*void initialise(int nn,int mm,int hh[]);
void cut(int l,int r,int k);
void magic(int i,int x);
long long inspect(int l,int r);*/
typedef long long ll;
il int read(){
    int x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-48,c=getchar();
    return x;
}
const int N=3e5+5,inf=1e9;
int n,m,a[N];
struct node{
    int mx,c,se;ll s;
    il node(){mx=c=se=0,s=0ll;}
}t[N<<2];int tag[N<<2];
il node merge(node x,node y){
    node z;z.s=x.s+y.s;
    if(x.mx>y.mx) z.mx=x.mx,z.c=x.c,z.se=max(x.se,y.mx);
    else if(x.mx<y.mx) z.mx=y.mx,z.c=y.c,z.se=max(x.mx,y.se);
    else z.mx=x.mx,z.c=x.c+y.c,z.se=max(x.se,y.se);
    return z;
}
il void pushup(int x){t[x]=merge(t[x<<1],t[x<<1|1]);}
il void maketag(int x,int w){if(w<t[x].mx) t[x].s-=1ll*(t[x].mx-w)*t[x].c,t[x].mx=w,tag[x]=w;}
il void pushdown(int x){if(tag[x]!=-inf) maketag(x<<1,tag[x]),maketag(x<<1|1,tag[x]),tag[x]=-inf;}
il void init(int x,int v){t[x].mx=v,t[x].c=1,t[x].se=-inf,t[x].s=1ll*v;}
void build(int x,int l,int r){
    tag[x]=-inf;
    if(l==r){init(x,a[l]);return ;}
    int mid=(l+r)>>1;
    build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    pushup(x);
}
void update(int x,int l,int r,int p,int v){
    if(l==r){init(x,v);return ;}
    int mid=(l+r)>>1;pushdown(x);
    if(p<=mid) update(x<<1,l,mid,p,v);
    else update(x<<1|1,mid+1,r,p,v);
    pushup(x);
}
void change(int x,int l,int r,int L,int R,int &k,int w){
    if(t[x].mx<w || k<=0) return ;
    if(l>=L && r<=R && ((w-1>t[x].se && k>=t[x].c) || l==r)){maketag(x,w-1),k-=t[x].c;return ;}
    int mid=(l+r)>>1;pushdown(x);
    if(L<=mid) change(x<<1,l,mid,L,R,k,w);
    if(R>mid) change(x<<1|1,mid+1,r,L,R,k,w);
    pushup(x);
}
void chmin(int x,int l,int r,int L,int R,int w){
    if(w>=t[x].mx) return ;
    if(l>=L && r<=R && (w>t[x].se || l==r)){maketag(x,w);return ;}
    int mid=(l+r)>>1;pushdown(x);
    if(L<=mid) chmin(x<<1,l,mid,L,R,w);
    if(R>mid) chmin(x<<1|1,mid+1,r,L,R,w);
    pushup(x);
}
node query(int x,int l,int r,int L,int R){
    if(l>=L && r<=R) return t[x];
    int mid=(l+r)>>1;pushdown(x);
    if(L>mid) return query(x<<1|1,mid+1,r,L,R);
    else if(R<=mid) return query(x<<1,l,mid,L,R);
    else return merge(query(x<<1,l,mid,L,R),query(x<<1|1,mid+1,r,L,R));
}
void initialise(int nn,int mm,int hh[]){
    n=nn,m=mm;for(int i=1;i<=n;++i) a[i]=hh[i];
    build(1,1,n);
}
void cut(int l,int r,int k){
    node cur;int x,y,z,u,v,w;
    while(k){
        cur=query(1,1,n,l,r);
        if(cur.mx<=0) break;
        if(k<cur.c) change(1,1,n,l,r,k,cur.mx);
        else x=max(cur.se,cur.mx-k/cur.c),chmin(1,1,n,l,r,x),k-=1ll*cur.c*(cur.mx-x);
    }
}
void magic(int x,int y){update(1,1,n,x,y);}
ll inspect(int l,int r){return query(1,1,n,l,r).s;}
//test:
/*int nn,mm,hh[N];
int opt,l,r,x,y,z,u,v,w;
int main(){
    scanf("%d%d",&nn,&mm);
    for(int i=1;i<=nn;++i) hh[i]=read();
    initialise(nn,mm,hh);
    while(mm--){
        opt=read();
        if(opt==1) l=read(),r=read(),x=read(),cut(l,r,x);
        else if(opt==2) x=read(),y=read(),magic(x,y);
        else l=read(),r=read(),printf("%lld\n",inspect(l,r));
    }
    return 0;
}*/