#include<bits/stdc++.h> using namespace std; #define int long long #define lson (pos<<1) #define rson (pos<<1|1) int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=200010,N=30,inf=1e18,Mod=1e9+7; void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;if(x<0)x+=Mod;} void Min(int &x,int y){x=min(x,y);} int n,m,q,a[MAXN],f[MAXN],l[MAXN],r[MAXN],id[MAXN]; stack<int>st; bool cmp(int x,int y){return a[x]>a[y];} struct segtree{ int t[MAXN<<2],lz[MAXN<<2]; void pushup(int pos){ t[pos]=t[lson]+t[rson]; } void upd(int pos,int l,int r,int x){ t[pos]+=x*(r-l+1); lz[pos]+=x; } void pushdown(int pos,int l,int r){ if(lz[pos])upd(lson,l,(l+r)>>1,lz[pos]),upd(rson,((l+r)>>1)+1,r,lz[pos]),lz[pos]=0; } void build(int pos,int l,int r){ if(l==r){ t[pos]=f[l]; return; } int mid=(l+r)>>1; build(lson,l,mid),build(rson,mid+1,r); pushup(pos); } void update(int pos,int l,int r,int x,int y){ // if(pos==1)cout<<x<<":"<<y<<endl; if(l==r){ t[pos]=y; return; } pushdown(pos,l,r); int mid=(l+r)>>1; if(x<=mid)update(lson,l,mid,x,y); if(x>mid)update(rson,mid+1,r,x,y); pushup(pos); } void update(int pos,int l,int r,int ql,int qr,int x){ if(ql<=l&&qr>=r){ upd(pos,l,r,x); return; } pushdown(pos,l,r); int mid=(l+r)>>1; if(ql<=mid)update(lson,l,mid,ql,qr,x); if(qr>mid)update(rson,mid+1,r,ql,qr,x); pushup(pos); } int query(int pos,int l,int r,int ql,int qr){ if(ql>qr||ql<1||qr>n)return 0; if(ql<=l&&qr>=r)return t[pos]; pushdown(pos,l,r); int mid=(l+r)>>1; if(qr<=mid)return query(lson,l,mid,ql,qr); if(ql>mid)return query(rson,mid+1,r,ql,qr); return query(lson,l,mid,ql,qr)+query(rson,mid+1,r,ql,qr); } void prt(int pos,int l,int r){ if(l==r){ cout<<t[pos]<<" "; return; } pushdown(pos,l,r); int mid=(l+r)>>1; prt(lson,l,mid),prt(rson,mid+1,r); } }F; struct sagtree{ int t[MAXN<<2]; void pushup(int pos){ t[pos]=max(t[lson],t[rson]); } void build(int pos,int l,int r){ if(l==r){ t[pos]=a[l]; return; } int mid=(l+r)>>1; build(lson,l,mid),build(rson,mid+1,r); pushup(pos); } void update(int pos,int l,int r,int x){ if(l==r){ t[pos]=a[l]; return; } int mid=(l+r)>>1; if(x<=mid)update(lson,l,mid,x); if(x>mid)update(rson,mid+1,r,x); pushup(pos); } int query(int pos,int l,int r,int x,int y){ if(x<1)return 0; if(x>n)return n+1; if(l==r)return t[pos]>=y?l:0; int mid=(l+r)>>1; if(x>mid&&x<=r){ int tmp=query(rson,mid+1,r,x,y); if(tmp)return tmp; else return query(lson,l,mid,x,y); } else if(x<=mid)return query(lson,l,mid,x,y); else if(x>r){ if(t[rson]>=y)return query(rson,mid+1,r,x,y); else return query(lson,l,mid,x,y); } } int quely(int pos,int l,int r,int x,int y){ if(x<1)return 0; if(x>n)return n+1; if(l==r)return t[pos]>=y?l:n+1; int mid=(l+r)>>1; if(x>=l&&x<=mid){ int tmp=quely(lson,l,mid,x,y); if(tmp<=n)return tmp; else return quely(rson,mid+1,r,x,y); } else if(x>mid)return quely(rson,mid+1,r,x,y); else if(x<l){ if(t[lson]>=y)return quely(lson,l,mid,x,y); else return quely(rson,mid+1,r,x,y); } } }A; void slv(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i]=read(),id[i]=i;a[0]=a[n+1]=inf; for(int i=1;i<=n;i++){ while(!st.empty()&&a[st.top()]<=a[i])st.pop(); l[i]=st.empty()?0:st.top(); st.push(i); } while(!st.empty())st.pop(); for(int i=n;i>=1;i--){ while(!st.empty()&&a[st.top()]<=a[i])st.pop(); r[i]=st.empty()?0:st.top(); st.push(i); } while(!st.empty())st.pop(); sort(id+1,id+n+1,cmp); for(int I=1;I<=n;I++){ int i=id[I]; if(a[l[i]]<a[r[i]])f[i]=f[l[i]]+1; else f[i]=f[r[i]]+1; } // for(int i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl; F.build(1,1,n),A.build(1,1,n); q=read(); while(q--){ int x=read(),l=read(),r=read(); if(a[x]==a[x+1]){ printf("%lld\n",(F.query(1,1,n,l,r)-r+l-1)*m+(n-1)*(r-l+1)); continue; } int k=a[x]; if(a[x]<a[x+1]){ if(x>1){ int k=A.query(1,1,n,x-1,a[x])+1; if(a[k-1]!=a[x])F.update(1,1,n,k,x-1,-1); } if(x+1<n){ k=A.quely(1,1,n,x+2,a[x])-1; if(a[k+1]!=a[x])F.update(1,1,n,x+1,k,1); } } else { int k; if(x>1){ k=A.query(1,1,n,x-1,a[x+1])+1; // cout<<" "<<k<<" "<<x<<endl; if(a[k-1]!=a[x+1])F.update(1,1,n,k,x-1,1); } if(x+1<n){ k=A.quely(1,1,n,x+2,a[x+1])-1; // cout<<" "<<k<<" "<<x<<endl; if(a[k+1]!=a[x+1])F.update(1,1,n,x+1,k,-1); } } swap(a[x],a[x+1]); A.update(1,1,n,x),A.update(1,1,n,x+1); if(a[x]>a[x+1]){ int L=A.query(1,1,n,x-1,a[x]+1),R=A.quely(1,1,n,x+1,a[x]+1); // cout<<"!"<<" "<<L<<" "<<R<<" "<<F.query(1,1,n,L,L)<<" "<<F.query(1,1,n,R,R)<<" "<<endl; if(a[L]<a[R])F.update(1,1,n,x,F.query(1,1,n,L,L)+1); else F.update(1,1,n,x,F.query(1,1,n,R,R)+1); L=A.query(1,1,n,x,a[x+1]+1),R=A.quely(1,1,n,x+2,a[x+1]+1); // cout<<"!"<<" "<<L<<" "<<R<<" "<<F.query(1,1,n,L,L)<<" "<<F.query(1,1,n,R,R)<<endl; if(a[L]<a[R])F.update(1,1,n,x+1,F.query(1,1,n,L,L)+1); else F.update(1,1,n,x+1,F.query(1,1,n,R,R)+1); } else{ int L=A.query(1,1,n,x,a[x+1]+1),R=A.quely(1,1,n,x+2,a[x+1]+1); if(a[L]<a[R])F.update(1,1,n,x+1,F.query(1,1,n,L,L)+1); else F.update(1,1,n,x+1,F.query(1,1,n,R,R)+1); L=A.query(1,1,n,x-1,a[x]+1),R=A.quely(1,1,n,x+1,a[x]+1); if(a[L]<a[R])F.update(1,1,n,x,F.query(1,1,n,L,L)+1); else F.update(1,1,n,x,F.query(1,1,n,R,R)+1); } printf("%lld\n",F.query(1,1,n,l,r)*m-(r-l+1)*m+(r-l+1)*(n-1)); // cout<<F.query(1,1,n,l,r)<<" "<<m<<endl; // F.prt(1,1,n);cout<<endl; // for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl; } } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); return 0; }