#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define ll long long using namespace std; const int N=2e5+10; int f[N],a[N],p[N]; int gl[N],gr[N]; int n,k,q; struct segtree{ int T[N<<2],len[N<<2]; ll F[N<<2],tg[N<<2]; #define ls p*2 #define rs p*2+1 #define mid (l+r)/2 void pu(int p){ T[p]=max(T[ls],T[rs]); F[p]=F[ls]+F[rs]; }void pd(int p){ F[ls]+=tg[p]*len[ls];tg[ls]+=tg[p]; F[rs]+=tg[p]*len[rs];tg[rs]+=tg[p]; tg[p]=0; }void bd(int p,int l,int r){ len[p]=r-l+1; if(l==r){ T[p]=a[l];F[p]=f[l]; return ; }bd(ls,l,mid);bd(rs,mid+1,r);pu(p); }int qrymx(int p,int l,int r,int pl,int pr){ if(pl<=l&&r<=pr) return T[p]; int mx=0; if(pl<=mid) mx=max(mx,qrymx(ls,l,mid,pl,pr)); if(pr>mid) mx=max(mx,qrymx(rs,mid+1,r,pl,pr)); return mx; }void mdf(int p,int l,int r,int x,pii v){ if(l==r){ T[p]=v.fi;F[p]=v.se; return ; }pd(p);if(x<=mid) mdf(ls,l,mid,x,v); else mdf(rs,mid+1,r,x,v);pu(p); }void upd(int p,int l,int r,int pl,int pr,int v){ if(pl>pr) return ; if(pl<=l&&r<=pr){ F[p]+=len[p]*v;tg[p]+=v; return ; }pd(p); if(pl<=mid) upd(ls,l,mid,pl,pr,v); if(pr>mid) upd(rs,mid+1,r,pl,pr,v); pu(p); }ll qryf(int p,int l,int r,int pl,int pr){ if(pl<=l&&r<=pr) return F[p]; ll sum=0;pd(p); if(pl<=mid) sum+=qryf(ls,l,mid,pl,pr); if(pr>mid) sum+=qryf(rs,mid+1,r,pl,pr); return sum; }int binl(int p,int l,int r,int x){ if(l==r){ if(T[p]<a[x+1]) return 0; else return l; } if(x<=mid){ return binl(ls,l,mid,x); }else if(x<=r){ int ps=binl(rs,mid+1,r,x); if(ps!=0) return ps; if(T[ls]>=a[x+1]) return binl(ls,l,mid,x); return 0; }else{ if(T[rs]>=a[x+1]) return binl(rs,mid+1,r,x); if(T[ls]>=a[x+1]) return binl(ls,l,mid,x); return 0; } }int binr(int p,int l,int r,int x){ if(l==r){ if(T[p]<a[x-1]) return n+1; else return l; } if(x>mid){ return binr(rs,mid+1,r,x); }else if(x>=l){ int ps=binr(ls,l,mid,x); if(ps!=n+1) return ps; if(T[rs]>=a[x-1]) return binr(rs,mid+1,r,x); return n+1; }else{ if(T[ls]>=a[x-1]) return binr(ls,l,mid,x); if(T[rs]>=a[x-1]) return binr(rs,mid+1,r,x); return n+1; } } #undef ls #undef rs #undef mid }sgt; int binl(int x){ return sgt.binl(1,1,n,x-1); } int binr(int x){ return sgt.binr(1,1,n,x+1); } void upd(int x){ a[x]++; int pl=binl(x),pr=binr(x);//cout<<a[pl]<<' '<<a[pr]<<' '<<a[x]-1<<endl; int mn=min(a[pl],a[pr]); ll mf=1e9+10; a[x]--;//cout<<pl<<' '<<pr<<endl; if(a[pl]==mn) mf=min(mf,((pl==0)?f[0]:sgt.qryf(1,1,n,pl,pl))); if(a[pr]==mn) mf=min(mf,((pr==n+1)?f[n+1]:sgt.qryf(1,1,n,pr,pr))); mf++;//cout<<x<<' '<<mf<<endl; sgt.mdf(1,1,n,x,mk(a[x],mf)); } int main(){ freopen("summer.in","r",stdin); freopen("summer.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; a[0]=1e9+10,a[n+1]=1e9+10;f[0]=-1;f[n+1]=-1; for(int i=1;i<=n;i++) p[i]=i; sort(p+1,p+n+1,[](int x,int y){return a[x]<a[y];}); stack<int> st;st.push(0); for(int i=1;i<=n+1;i++){ while(!st.empty()){ int p=st.top();//cout<<p<<' '<<i<<endl; if(a[p]>a[i]){ gl[i]=p;break; }else if(a[p]<a[i]){ gr[p]=i;st.pop(); }else{ gl[i]=gl[p];break; } }st.push(i); }for(int i=n;i>=1;i--){ int id=p[i];//cout<<a[id]<<' '<<a[gr[id]]<<endl; int mn=min(a[gl[id]],a[gr[id]]); int val=1e9+10; if(a[gl[id]]==mn) val=min(val,f[gl[id]]); if(a[gr[id]]==mn) val=min(val,f[gr[id]]); f[id]=val+1;//cout<<f[id]<<' '<<id<<' '<<gl[id]<<' '<<gr[id]<<endl; }sgt.bd(1,1,n); cin>>q; while(q--){ int x,l,r;cin>>x>>l>>r; //for(int i=1;i<=n;i++) cout<<sgt.qryf(1,1,n,i,i)<<' ';cout<<endl; int pl,pr; if(a[x]<a[x+1]) pl=binl(x); if(a[x]>a[x+1]) pr=binr(x+1); swap(a[x],a[x+1]); if(a[x]>a[x+1]) pr=binr(x+1); if(a[x]<a[x+1]) pl=binl(x); if(a[x]>a[x+1]){ if(a[pl]!=a[x+1]) sgt.upd(1,1,n,pl+1,x-1,-1); if(a[pr]!=a[x+1]) sgt.upd(1,1,n,x+1,pr-1,1); }if(a[x]<a[x+1]){ if(a[pl]!=a[x]) sgt.upd(1,1,n,pl+1,x-1,1); if(a[pr]!=a[x]) sgt.upd(1,1,n,x+1,pr-1,-1); } sgt.mdf(1,1,n,x,mk(a[x],0)); sgt.mdf(1,1,n,x+1,mk(a[x+1],0)); if(a[x]>a[x+1]) upd(x),upd(x+1); else upd(x+1),upd(x); //for(int i=1;i<=n;i++) cout<<sgt.qryf(1,1,n,i,i)<<' ';cout<<endl; //cout<<sgt.qryf(1,1,n,3,3)<<endl; cout<<sgt.qryf(1,1,n,l,r)*k+1ll*(n-1)*(r-l+1)<<'\n'; }cout.flush(); /*cout<<"100000 1"<<endl; for(int i=1;i<=100000;i++) cout<<1<<' ';cout<<endl; cout<<"100000"<<endl; for(int i=1;i<=100000;i++) cout<<1<<' '<<1<<' '<<1<<endl;*/ return 0; }