#define D90 struct Writer{typedef __int128 mxdouble;template<typename T>typename std::enable_if_t<std::is_class<T>::value,Writer&>operator<<(const T&x){for(auto q:x){*this<<q;if(!is_class<decltype(q)>::value)*this<<print_between;}if(!is_class<typename T::value_type>::value&&print_T_endl)*this<<'\n';return *this;}template<typename...T>Writer&operator<<(const std::tuple<T...>&x){print_tuple<sizeof...(T)>::print(*this,x);if(print_T_endl)*this<<'\n';return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Writer&>operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Writer&>operator<<(T x){if(x<0)putchar('-'),x=-x;x+=pow(10,-print_precision)/2;mxdouble _=x;x-=(T)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<print_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<print_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Writer&>operator<<(const T&c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}template<typename T1,typename T2>Writer&operator<<(const std::pair<T1,T2>&x){*this<<x.first<<print_between<<x.second;if(print_T_endl)*this<<'\n';return *this;}Writer&operator<<(const std::string&str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}
#define D8F struct Reader{template<typename T>typename std::enable_if_t<std::is_class<T>::value,Reader&>operator>>(T&x){for(auto &y:x)*this>>y;return *this;}template<typename...T>Reader&operator>>(std::tuple<T...>&x){read_tuple<sizeof...(T)>::read(*this,x);return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1;while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;return *this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1,s=0;x=0;T t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Reader&>operator>>(T&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}template<typename T1,typename T2>Reader&operator>>(std::pair<T1,T2>&x){*this>>x.first>>x.second;return *this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';
#define D8E namespace Fread{const int SIZE=1<<16;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}namespace Fwrite{const int SIZE=1<<16;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}
#define D8D clock_t time_last;time_helper(){time_last=clock();}void test(){auto time_now=clock();std::cerr<<"time:"<<1.*(time_now-time_last)/CLOCKS_PER_SEC<<";all_time:"<<1.*time_now/CLOCKS_PER_SEC<<std::endl;time_last=time_now;}~time_helper(){test();}
#define D8C std::tuple<T...>&x){print_tuple<id-1>::print(stream,x);putchar(print_between);stream<<get<id-1>(x);}};template<>struct
#define D8B read(Reader&stream,std::tuple<T...>&x){read_tuple<id-1>::read(stream,x);stream>>get<id-1>(x);}};template<>struct
#define D8A value=(std::is_integral<T>::value||std::is_same<T,__int128>::value)&&!is_char<T>::value;};template<typename
#define D89 read([[maybe_unused]]Reader&stream,[[maybe_unused]]std::tuple<T...>&x){}};template<size_t
#define D88 value=std::is_floating_point<T>::value||std::is_same<T,__float128>::value;};namespace
#define D87 cin>>a[x],bl[x]=(x-1)/B+1,L[bl[x]]=(bl[x]==bl[x-1]?L[bl[x]]:x),R[bl[x]]=x;
#define D86 int print_precision=10;bool print_T_endl=1;char print_between=' ';
#define D85 y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));}
#define D84 std::tuple<T...>&x){stream<<get<0>(x);}};template<>struct
#define D83 value=(std::is_same<T,char>::value||std::is_same<T,signed
#define D82 print([[maybe_unused]]Writer&stream,[[maybe_unused]]const
#define D81 b0[y+L[x]-1]+=tag1[x][y]+tag2[x][y]*premx[y+L[x]-1];
#define D80 pos=lower_bound(premx+L[x],premx+R[x]+1,mx)-premx;
#define D7F sufsum[y]=y==R[x]?premx[y]:sufsum[y+1]+premx[y];
#define D7E std::forward<Args>(args)...);}};template<class
#define D7D tag1[N/B+5][B+5],tag2[N/B+5][B+5],sum[N/B+5];
#define D7C a[N+5],L[N/B+5],R[N/B+5],bl[N+5],premx[N+5];
#define D7B print_tuple<1>{template<typename...T>static
#define D7A print_tuple<0>{template<typename...T>static
#define D79 premx[y]=y==L[x]?a[y]:max(a[y],premx[y-1]);
#define D78 read_tuple<0>{template<typename...T>static
#define D77 print_tuple{template<typename...T>static
#define D76 read_tuple{template<typename...T>static
#define D75 sum[x]+=1ll*mx*(pos-L[x])+sufsum[pos];
#define D74 char>::value||std::is_same<T,unsigned
#define D73 mx=max(mx,a[x]),b0[x]+=mx,sum[b]+=mx;
#define D72 memset(tag1[x],0,sizeof(tag1[x]));
#define D71 memset(tag2[x],0,sizeof(tag2[x]));
#define D70 char>::value);};template<typename
#define D6F if(bl[l]==bl[r])brute(l,r,mx);
#define D6E is_floating_point_ex{static
#define D6D fun_;public:template<class
#define D6C fun_(std::forward<T>(fun))
#define D6B tc=1;tc<=t;tc++)solve(tc);
#define D6A tag2[x][y]+=tag2[x][y-1],
#define D69 tag1[x][y]+=tag1[x][y-1],
#define D68 print(Writer&stream,const
#define D67 x=bl[l]+1;x<=bl[r]-1;x++)
#define D66 solve([[maybe_unused]]int
#define D65 ans+=bruteq(L[bl[r]],r);
#define D64 tag1[x][pos-L[x]+1]-=mx;
#define D63 std::tuple<T...>&x){}};
#define D62 ans=bruteq(l,R[bl[l]]);
#define D61 y_combinator_result{Fun
#define D60 y=1;y<=R[x]-L[x]+1;y++)
#define D5F tag2[x][pos-L[x]+1]++;
#define D5E Writer;template<size_t
#define D5D ...Args>decltype(auto)
#define D5C brute(L[bl[r]],r,mx);
#define D5B brute(l,R[bl[l]],mx);
#define D5A is_integral_ex{static
#define D59 fun_(std::ref(*this),
#define D58 y_combinator_result(T
#define D57 sum[x]+=sufsum[L[x]];
#define D56 sufsum[N+5],b0[N+5];
#define D55 y=L[x];y<=R[x];y++)
#define D54 y=R[x];y>=L[x];y--)
#define D53 if(premx[R[x]]<=mx)
#define D52 if(premx[L[x]]>=mx)
#define D51 Fun>decltype(auto)
#define D50 sum[x]+=1ll*mx*B;
#define D4F template<typename
#define D4E x=1;x<=bl[n];x++)
#define D4D &&...args){return
#define D4C if(bl[l]==bl[r])
#define D4B if(l>r)continue;
#define D4A cout<<ans<<endl;
#define D49 {}template<class
#define D48 y_combinator(Fun
#define D47 ans=bruteq(l,r);
#define D46 mx=premx[R[x]];
#define D45 B=500,N=500000;
#define D44 operator()(Args
#define D43 tag1[x][1]+=mx;
#define D42 cin>>op>>l>>r;
#define D41 template<class
#define D40 is_char{static
#define D3F }time_helper;
#define D3E x=l;x<=r;x++)
#define D3D tag2[x][1]++;
#define D3C &&fun){return
#define D3B Fastio{struct
#define D3A Reader;struct
#define D39 apply(bl[l]);
#define D38 apply(bl[r]);
#define D37 build(bl[l]);
#define D36 x=1;x<=n;x++)
#define D35 ans+=sum[x];
#define D34 time_helper{
#define D33 init();void
#define D32 res+=b0[x];
#define D31 cin>>n>>m;
#define D30 bruteq(int
#define D2F while(m--)
#define D2E T>explicit
#define D2D init();int
#define D2C apply(int
#define D2B if(op==3)
#define D2A solve(int
#define D29 if(op==2)
#define D28 constexpr
#define D27 brute(int
#define D26 build(x);
#define D25 id>struct
#define D24 Fun>class
#define D23 build(int
#define D22 if(op==1)
#define D21 namespace
#define D20 r,int&mx)
#define D1F b=bl[l];
#define D1E __int128
#define D1D test(){}
#define D1C T>struct
#define D1B for(int
#define D1A a[l]=r;
#define D19 &&fun):
#define D18 op,l,r;
#define D17 return
#define D16 struct
#define D15 res=0;
#define D14 ans=0;
#define D13 init()
#define D12 main()
#define D11 l,int
#define D10 mx=0;
#define DF using
#define DE else
#define DD std;
#define DC bool
#define DB long
#define DA void
#define D9 n,m;
#define D8 tc);
#define D7 res;
#define D6 t=1;
#define D5 tc)
#define D4 int
#define D3 x)
#define D2 r)
#define D1 {
#define D0 }
#include <time.h>
#include<bits/stdc++.h>
#define D91 DF D21 DD D16 D34 
#define D92(__FOX__) __FOX__
D92(D91)
#ifdef LOCAL
#define D93 D8D 
#define D94(__FOX__) __FOX__
D94(D93)
#else
#define D95 DA D1D 
#define D96(__FOX__) __FOX__
D96(D95)
#endif
#define D97 D3F 
#define D98(__FOX__) __FOX__
D98(D97)
#ifdef LOCAL
#include"dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif
#define D99 D8E 
#define D9A(__FOX__) __FOX__
D9A(D99)
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#define D9B D86 D4F D1C D40 D28 DC D83 D74 D70 D1C
#define D9C D5A D28 DC D8A D1C D6E D28 DC D88 D3B
#define D9D D3A D5E D25 D76 DA D8B D78 DA D89 D25
#define D9E D77 DA D68 D8C D7B DA D68 D84 D7A DA
#define D9F D82 D63 D8F D90 
#define DA0 D9B D9C D9D D9E D9F 
#define DA1(__FOX__) __FOX__
DA1(DA0)
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
#define DA2 D41 D24 D61 D6D D2E D58 D19 D6C D49 D5D
#define DA3 D44 D4D D59 D7E D51 D48 D3C D85 DA D33
#define DA4 D2A D8 D12 D1 D2D D6 D1B D6B D0 DA
#define DA5 D13 D1 D0 D28 D4 D45 D4 D7C DB DB
#define DA6 D56 DA D23 D3 D1 D1B D55 D79 D1B D54
#define DA7 D7F D0 DB DB D7D DA D2C D3 D1 D1B
#define DA8 D60 D69 D6A D81 D72 D71 D0 DA D27 D11
#define DA9 D20 D1 D4 D1F D1B D3E D73 D0 DB DB
#define DAA D30 D11 D2 D1 DB DB D15 D1B D3E D32
#define DAB D17 D7 D0 DA D66 D5 D1 D4 D9 D31
#define DAC D1B D36 D87 D1B D4E D26 D2F D1 D4 D18
#define DAD D42 D22 D1 D39 D1A D37 D0 D4B D29 D1
#define DAE D4 D10 D6F DE D1 D5B D1B D67 D1 D53
#define DAF D1 D43 D50 D0 DE D52 D1 D3D D57 D46
#define DB0 D0 DE D1 D4 D80 D43 D64 D5F D75 D46
#define DB1 D0 D0 D5C D0 D0 D2B D1 D1E D14 D4C
#define DB2 D1 D39 D47 D0 DE D1 D39 D38 D62 D1B
#define DB3 D67 D35 D65 D0 D4A D0 D0 D0 
#define DB4 DA2 DA3 DA4 DA5 DA6 DA7 DA8 DA9 DAA DAB
#define DB5 DAC DAD DAE DAF DB0 DB1 DB2 DB3 
#define DB6 DB4 DB5 
#define DB7(__FOX__) __FOX__
DB7(DB6)