#include<bits/stdc++.h>
using namespace std;
int n;
#define pi pair<int,int>
const int N=5e5+10;
#define pb push_back
#define pi pair<int,int>
#define fi first
#define se second
vector<pi>G[N],H[N],Q[N];int a[N],q;
#define ll long long
ll ans[N];
ll sb[N<<2],s1[N<<2],s2[N<<2],mi[N<<2],mi2[N<<2],t1[N<<2],t2[N<<2],t3[N<<2];
//t1:把 max 都改成 t2 
//t2:b+=a*t1
//t3:对于mx的位置, b+=t3
void sc(int p){
    int l=(p<<1),r=(p<<1|1);
    mi[p]=min(mi[l],mi[r]),mi2[p]=min(mi2[l],mi2[r]);
    if(mi[l]!=mi[r])mi2[p]=min(mi2[p],max(mi[l],mi[r]));
    sb[p]=sb[l]+sb[r],s1[p]=s2[p]=0;
    for(int o=0;o<2;o++){
        if(mi[l]<=mi[r])s1[p]+=s1[l],s2[p]+=s2[l];
        else s1[p]+=s1[l]+mi[l]*s2[l];
        swap(l,r);
    }
}
void uc(int p,ll z1,ll z2,ll z3){
    sb[p]+=s1[p]*z2+s2[p]*z3;
    if(z1)mi[p]=z1,t1[p]=z1;
    t2[p]+=z2,t3[p]+=z3;
}
void pd(int p){
    int l=(p<<1),r=(p<<1|1);
    for(int o=0;o<2;o++){
        if(mi[l]<=mi[r])
            uc(l,t1[p],t2[p],t3[p]);
        else 
            uc(l,0,t2[p],t2[p]*mi[l]);
        swap(l,r);
    }
    t1[p]=t2[p]=t3[p]=0;
}
ll ask(int p,int l,int r,int x){
    if(l==r)return sb[p];
    pd(p);int mid=(l+r)>>1;
    if(x<=mid)return ask(p<<1,l,mid,x);
    return sb[p<<1]+ask(p<<1|1,mid+1,r,x);
}
void up(int p,int l,int r,int x,int y,int z){
    if(mi[p]>=z)return;
    if(x<=l&&r<=y&&z<mi2[p])return uc(p,z,0,0);
    pd(p);int mid=(l+r)>>1;
    if(x<=mid)up(p<<1,l,mid,x,y,z);
    if(y>mid)up(p<<1|1,mid+1,r,x,y,z);
    sc(p);
}
void up2(int p,int l,int r,int x,int z){
    if(l==r){
        mi[p]=0,mi2[p]=1e9+7;
        s1[p]=0,s2[p]=z;
        return;
    }
    pd(p);int mid=(l+r)>>1;
    if(x<=mid)up2(p<<1,l,mid,x,z);
    else up2(p<<1|1,mid+1,r,x,z);
    sc(p);
}
bool aq[N];
int main(){
    int q;
    scanf("%d%d",&n,&q);
    for(int i=1,x;i<=n;i++)scanf("%d",&x),G[i].pb({x,1});
    for(int i=1,op,x,y;i<=q;i++){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)G[x].pb({y,i+1});
        if(op==2)H[x].pb({i,1}),H[y+1].pb({i,0});
        if(op==3)Q[x-1].pb({i,-1}),Q[y].pb({i,1}),aq[i]=1;
    }
    for(int i=1;i<=q*4;i++)mi2[i]=1e9+7;
    for(int i=1;i<=n;i++){
        for(pi o:H[i])up2(1,1,q,o.fi,o.se);
        int sz=G[i].size();
        for(int j=0;j<sz;j++)if(G[i][j].se<=q)
        up(1,1,q,G[i][j].se,((j!=sz-1)?(G[i][j+1].se-1):q),G[i][j].fi);
        uc(1,0,1,mi[1]);
        for(pi o:Q[i])
        ans[o.fi]+=ask(1,1,q,o.fi)*o.se;
    }
    for(int i=1;i<=q;i++)if(aq[i])printf("%lld\n",ans[i]);
    return 0;
}