#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,k,q,a[maxn],pre[maxn],nxt[maxn],stk[maxn];ll f[maxn]; inline ll F(int i){ if(f[i]!=-1)return f[i]; if(pre[i]==0&&nxt[i]==n+1)return 0; return f[i]=a[pre[i]]<a[nxt[i]]?F(pre[i])+k:F(nxt[i])+k; } struct SegTree { struct nd { int mx,lz,len;ll sm; void push(ll x){ lz+=x,sm+=len*x; } }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define mx(p) d[p].mx #define lz(p) d[p].lz #define sm(p) d[p].sm #define len(p) d[p].len void pu(int p){sm(p)=sm(ls(p))+sm(rs(p)),mx(p)=max(mx(ls(p)),mx(rs(p)));} void pd(int p){d[ls(p)].push(d[p].lz),d[rs(p)].push(d[p].lz),d[p].lz=0;} void bd(int l,int r,int p){ d[p].len=r-l+1; if(l==r)return d[p].mx=a[l],d[p].sm=::F(l)+n-1,void(); int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); } void modify(int l,int r,int s,int t,int p,int k){if(l>r)return; if(l<=s&&t<=r)return d[p].push(k);pd(p); int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),k);if(r>mid)modify(l,r,mid+1,t,rs(p),k);pu(p); } void upd(int l,int s,int t,int p){ if(s==t)return d[p].mx=a[l],void();pd(p); int mid=s+t>>1; if(l<=mid)upd(l,s,mid,ls(p));else upd(l,mid+1,t,rs(p));pu(p); }void updf(int l,int s,int t,int p,ll x){ if(s==t)return d[p].sm=x,void();pd(p); int mid=s+t>>1; if(l<=mid)updf(l,s,mid,ls(p),x);else updf(l,mid+1,t,rs(p),x);pu(p); } ll ask(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return d[p].sm;pd(p); int mid=s+t>>1;ll res=0; if(l<=mid)res+=ask(l,r,s,mid,ls(p));if(r>mid)res+=ask(l,r,mid+1,t,rs(p)); return res; } int F(int s,int t,int p,int lim){ if(s==t)return s; int mid=s+t>>1; if(d[rs(p)].mx>lim)return F(mid+1,t,rs(p),lim); return F(s,mid,ls(p),lim); } int G(int s,int t,int p,int lim){ if(s==t)return s; int mid=s+t>>1; if(d[ls(p)].mx>lim)return G(s,mid,ls(p),lim); return G(mid+1,t,rs(p),lim); } int askmx(int l,int r,int s,int t,int p,int lim){ if(l<=s&&t<=r){ if(d[p].mx>lim)return F(s,t,p,lim); return 0; }int mid=s+t>>1,res=0; if(r>mid)res=askmx(l,r,mid+1,t,rs(p),lim);if(res)return res; if(l<=mid)return askmx(l,r,s,mid,ls(p),lim); return 0; } int askmx2(int l,int r,int s,int t,int p,int lim){ if(l<=s&&t<=r){ if(d[p].mx>lim)return G(s,t,p,lim); return 0; }int mid=s+t>>1,res=0; if(l<=mid)res=askmx2(l,r,s,mid,ls(p),lim);if(res)return res; if(r>mid)return askmx2(l,r,mid+1,t,rs(p),lim); return 0; } }T; int getpre(int u,int lim){ if(a[u]>lim)return u+1; int k=T.askmx(1,u,1,n,1,lim); return k+1; } int getnxt(int u,int lim){ if(a[u]>lim)return u-1; int k=T.askmx2(u,n,1,n,1,lim); if(k)k--;else k=n;return k; } void upd(int u){ int p=getpre(u-1,a[u])-1,q=getnxt(u+1,a[u])+1; if(a[p]<a[q])T.updf(u,1,n,1,T.ask(p,p,1,n,1)+k); else T.updf(u,1,n,1,((q<=n)?T.ask(q,q,1,n,1)+k:n-1)); } void update(int u){ if(a[u]<=a[u+1]){ T.modify(getpre(u-1,a[u]-1),u-1,1,n,1,-k); T.modify(u+2,getnxt(u+2,a[u]-1),1,n,1,k); }else { T.modify(getpre(u-1,a[u+1]-1),u-1,1,n,1,k); T.modify(u+2,getnxt(u+2,a[u+1]-1),1,n,1,-k); } swap(a[u],a[u+1]); T.upd(u,1,n,1),T.upd(u+1,1,n,1); if(a[u]<=a[u+1])upd(u+1),upd(u); else upd(u),upd(u+1); } void slv(){ n=read(),k=read(); up(i,1,n)a[i]=read(); a[0]=1e9,a[n+1]=1e9; int tp=0;stk[0]=0; up(i,1,n){ while(tp&&a[stk[tp]]<=a[i])tp--; pre[i]=stk[tp];stk[++tp]=i; } stk[tp=0]=n+1; down(i,n,1){ while(tp&&a[stk[tp]]<=a[i])tp--; nxt[i]=stk[tp];stk[++tp]=i; f[i]=-1; } T.bd(1,n,1); q=read(); while(q--){ int x=read(),l=read(),r=read();update(x); printf("%lld\n",T.ask(l,r,1,n,1)); } } int main(){ //freopen("summer.in","r",stdin),freopen("summer.out","w",stdout); slv(); return 0; }