#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
struct Splay
{
int p, l, r, v, cnt;
long long sum;
bool inv;
Splay() : p(0), l(0), r(0), v(0), cnt(1), sum(0), inv(false) {}
} tree[200003];
vector<tuple<int,int,int,int>> Q;
vector<int> C, T;
int root, color[200001];
long long ans[200000];
int find_(int a)
{
return color[a]=a==color[a] ? a:find_(color[a]);
}
void union_(int a, int b)
{
a=find_(a); b=find_(b);
color[a]=color[b]=max(a,b);
}
void lazy(int c)
{
if(tree[c].inv) {
swap(tree[c].l,tree[c].r);
if(tree[c].l) tree[tree[c].l].inv^=1;
if(tree[c].r) tree[tree[c].r].inv^=1;
tree[c].inv=false;
}
}
void update(int c)
{
tree[c].cnt=tree[tree[c].l].cnt+tree[tree[c].r].cnt+1;
tree[c].sum=tree[tree[c].l].sum+tree[tree[c].r].sum+tree[c].v;
}
void rotate(int c)
{
int p=tree[c].p;
if(tree[p].l==c) {
if(tree[c].r) tree[tree[c].r].p=p;
tree[p].l=tree[c].r;
tree[c].r=p;
}
else {
if(tree[c].l) tree[tree[c].l].p=p;
tree[p].r=tree[c].l;
tree[c].l=p;
}
if(tree[p].p) (tree[tree[p].p].l==p ? tree[tree[p].p].l:tree[tree[p].p].r)=c;
tree[c].p=tree[p].p;
tree[p].p=c;
update(p); update(c);
}
void splay(int c)
{
while(tree[c].p) {
int p=tree[c].p;
if(tree[p].p) lazy(tree[p].p);
lazy(p); lazy(c);
if(tree[p].p) rotate((tree[tree[p].p].l==p)==(tree[p].l==c) ? p:c);
rotate(c);
}
lazy(root=c);
}
int kth(int k)
{
int c=root;
for(;;) {
lazy(c);
if(tree[tree[c].l].cnt>k) {
c=tree[c].l;
continue;
}
k-=tree[tree[c].l].cnt;
if(!k--) break;
c=tree[c].r;
}
splay(c);
return c;
}
int interval(int l, int r)
{
int ret, temp;
kth(l-1);
temp=root;
root=tree[root].r;
tree[root].p=0;
kth(r-l+1);
tree[temp].r=root;
ret=tree[root].l;
tree[root].p=temp;
update(root=temp);
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, M, j=0;
cin>>N>>M; tree[0].cnt=0;
for(int i=1;i<=N;i++) {
cin>>tree[i+1].v;
tree[i+1].l=i;
tree[i].p=i+1;
update(i+1);
color[i]=i;
if(tree[i].v>=tree[i+1].v) union_(i-1,i);
}
tree[N+2].l=N+1;
root=tree[N+1].p=N+2;
update(N+2);
Q.resize(M);
for(int i=0;i<M;i++) {
auto &[t,l,r,idx]=Q[i];
cin>>t>>l>>r; idx=i;
}
sort(Q.begin(),Q.end());
for(int c=1;c<=N;c=find_(c)+1) {
int n=find_(c), i, j;
i=kth(c); j=kth(n);
if(tree[i].v>tree[j].v) C.push_back(c);
}
for(int t=1;t<=N;t++) {
for(auto c: C) {
int n=find_(c), v, p;
v=tree[kth(c)].v;
tree[interval(c,n-1)].inv^=1;
tree[interval(c,n)].inv^=1;
tree[kth(c)].v=v;
update(root);
if(n<N) {
p=kth(n); v=kth(n+1);
if(tree[p].v>=tree[v].v) union_(n,n+1);
}
}
T.clear();
for(auto c: C) if(find_(c-1)!=find_(c) && tree[kth(c)].v>tree[kth(find_(c))].v) T.push_back(c);
C=T;
while(j<M && get<0>(Q[j])==t) {
auto[t,l,r,idx]=Q[j++];
ans[idx]=tree[interval(l,r)].sum;
}
}
for(int i=0;i<M;i++) cout<<ans[i]<<'\n';
return 0;
}
