#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cstring> 
#include<map>
#include<set>
using namespace std;  
#define int long long 
#define ri register int
#define rd(n) n=read()
inline int read(void)
{
    register int res=0,f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){f^=(c=='-');c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
    return f?-res:res;
}
inline void fprint(int n)
{
    if(n<0){putchar('-');n=-n;}
    if(n>9) fprint(n/10);
    putchar(n%10+'0');
}
inline void print(int n)
{
    fprint(n);
    putchar('\n');
}
const int N=200005; 
const int INF=2147483647;
int n,m,k,x,y,z,ans,res,tot,a[N];
#define ls(p) p<<1
#define rs(p) p<<1|1
struct SegmentTreeBeats{
	int l,r,ma;
	int nm,ns,se;
	#define l(p) t[p].l
	#define r(p) t[p].r
	#define ma(p) t[p].ma
	#define se(p) t[p].se
	#define nm(p) t[p].nm
	#define ns(p) t[p].ns
}t[N<<2];
int op;
inline void pushup(int p)
{
	if(ma(ls(p))>ma(rs(p)))
    {
        ma(p)=ma(ls(p));
        nm(p)=nm(ls(p));
        if(ma(rs(p))>se(ls(p)))
		{
			se(p)=ma(rs(p));
			ns(p)=nm(rs(p));
		}
        else 
		{
			se(p)=se(ls(p));
			ns(p)=ns(ls(p));
		}
    }
    if(ma(ls(p))<ma(rs(p)))
    {
    	ma(p)=ma(rs(p));
        nm(p)=nm(rs(p));
        if(ma(ls(p))>se(rs(p)))
		{
			se(p)=ma(ls(p));
			ns(p)=nm(ls(p));
		}
        else 
		{ 
    		se(p)=se(rs(p));
    		ns(p)=ns(rs(p));
		}
	}
    if(ma(ls(p))==ma(rs(p)))
    {
    	ma(p)=ma(ls(p));
    	nm(p)=nm(ls(p))+nm(rs(p));
        if(se(ls(p))>se(rs(p)))
		{
			se(p)=se(ls(p));
			ns(p)=ns(ls(p));
		}
        else 
        {
			se(p)=se(rs(p));
			ns(p)=ns(rs(p));
		}
    }
}
void build(int p,int l,int r)
{
	l(p)=l; r(p)=r;
	if(l==r)
	{
		ma(p)=a[l];
		nm(p)=1;
		se(p)=-2;
		ns(p)=0;
		return;
	}
	ri mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
}
void change(int p,int x,int v)
{
	if(l(p)==r(p))
	{
		ma(p)=v;
		return;
	}
	ri mid=(l(p)+r(p))>>1;
	if(x<=mid) change(ls(p),x,v);
	else change(rs(p),x,v);
	pushup(p);
}
int ask(int p,int l,int r)
{
    if(l<=l(p)&&r>=r(p)) return ma(p); 
    int mid=(l(p)+r(p))>>1; 
	int ans=-1147483647;
    if(l<=mid) ans=max(ans,ask(ls(p),l,r)); 
    if(r>mid) ans=max(ans,ask(rs(p),l,r)); 
    return ans;
} 
struct node{
	int x,y,z,phi;
};
inline node query(int p,int l,int r,int mx)
{
	if(l<=l(p)&&r(p)<=r) return (node){ma(p),se(p),nm(p),ns(p)};
	ri mid=(l(p)+r(p))>>1; 
	int res=-1;
	node q1=(node){-1,-2,0,0};
	node q2=(node){-1,-2,0,0};
	if(l<=mid) q1=query(ls(p),l,r,mx);
	if(r>mid) q2=query(rs(p),l,r,mx);
	ri tt=0;
	ri sec=-2,nse=0;
	if(q1.x!=mx) 
	{
		if(q1.x==res) ans+=q1.z;
		if(q1.x>res)
		{
			res=q1.x;
			ans=q1.z;
		} 
	}
	if(q2.x!=mx) 
	{
		if(q2.x==res) ans+=q2.z;
		if(q2.x>res)
		{
			res=q2.x;
			ans=q2.z;
		} 
	}
	if(q1.y==res) ans+=q1.phi;
	if(q1.y>res)
	{
		res=q1.y;
		ans=q1.phi;
	}
	if(q2.y==res) ans+=q2.phi;
	if(q2.y>res)
	{
		res=q2.y;
		ans=q2.phi;
	}
	if(q1.x==q2.x) 
	{
		if(q1.y>q2.y)
		{
			sec=q1.y;
			nse=q1.phi;
		}
		if(q1.y<q2.y)
		{
			sec=q2.y;
			nse=q2.phi;
		} 
		if(q1.y==q2.y)
		{
			sec=q2.y;
			nse=q2.phi+q1.phi;
		} 
	}
	else 
	{
		if(q1.x>q2.x)
		{
			sec=q2.x;
			nse=q2.z;
		}
		else
		{
			sec=q1.x;
			nse=q1.z;
		}
	} 
	tt=0;
	if(q1.x==q2.x) tt=q1.z+q2.z;
	else tt=q1.x>q2.x?q1.z:q2.z;
	return (node){max(q1.x,q2.x),sec,tt,nse};
}
signed main(void)
{ 
	rd(n); rd(m);
	for(ri i=1;i<=n;++i) rd(a[i]);
	build(1,1,n);
	while(m--)
	{
		rd(op);
		if(op&1)
		{
			rd(x); rd(y);
			change(1,x,y);
		}
		else
		{
			rd(x); rd(y); 
			ri mas=ask(1,x,y);
			ans=0;
			query(1,x,y,mas);
			print(ans);
		}
	}
	return 0;
}
/*
5 2
2 1 4 2 3
2 1 3
2 1 4

5 4
3 3 1 4 5
2 1 3
2 5 5
1 3 3
2 2 4

5 1
3 3 3 4 5
2 2 4

8 9
2 4 4 3 9 1 1 2
1 5 4
2 7 7
2 2 6
1 4 4
2 2 5
2 2 7
1 1 1
1 8 1
2 1 8

*/