wrong answer 2322nd numbers differ - expected: '5', found: '6'

//f([l,r])=min_{i=l+k-1}^{r}(g[i])
#include <bits/stdc++.h>
#define ver 3
using namespace std;
const int N=200007;
typedef long long li;
const li inf=0xc0c0c0c0c0c0c0c0;
li a[N],g[N],ans[N];
struct segtree1{
	int val[N<<3];
	#define ls(o) o*2
	#define rs(o) o*2+1
	void update(int o){val[o]=max(val[ls(o)],val[rs(o)]);}
	void build(int l,int r,int o){
		val[o]=0;
		if(l==r) return;
		int mid=(l+r)>>1;
		build(l,mid,ls(o)),build(mid+1,r,rs(o));
	}
	void add(int x,int ll,int rr,int o,int v){
		if(ll==rr) return void(val[o]+=v);
		int mid=(ll+rr)>>1;
		if(x<=mid) add(x,ll,mid,ls(o),v);
		if(x>mid) add(x,mid+1,rr,rs(o),v);
		update(o);
	}
} tt;
struct segtree{
	li val[N<<2],lz[N<<2];
	#define ls(o) o*2
	#define rs(o) o*2+1
	void update(int o){val[o]=val[ls(o)]+val[rs(o)];}
	void build(int l,int r,int o){
		val[o]=lz[o]=0;
		if(l==r) return;
		int mid=(l+r)>>1;
		build(l,mid,ls(o)),build(mid+1,r,rs(o));
	}
	void add(int o,int l,int r,int v){val[o]+=1ll*(r-l+1)*v,lz[o]+=v;}
	void pushdown(int o,int l,int r){
		if(lz[o]) add(o,l,r,lz[o]);
		lz[o]=0;
	}
	void add(int l,int r,int ll,int rr,int o,int v){
		if(l<=ll&&rr<=r) return add(o,ll,rr,v);
		pushdown(o,ll,rr);
		int mid=(ll+rr)>>1;
		if(l<=mid) add(l,r,ll,mid,ls(o),v);
		if(r>mid) add(l,r,mid+1,rr,rs(o),v);
		update(o);
	}
	li query(int l,int r,int ll,int rr,int o){
		if(l<=ll&&rr<=r) return val[o];
		li ans=0;
		pushdown(o,ll,rr);
		int mid=(ll+rr)>>1;
		if(l<=mid) ans+=query(l,r,ll,mid,ls(o));
		if(r>mid) ans+=query(l,r,mid+1,rr,rs(o));
		return ans;
	}
} tr;
struct query{int t,r;}; vector<query> q[N];
struct node{li pos,val;} st[N],*tp=st;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin>>t;
	while(t-->0){
		int n,k,qq;
		cin>>n>>k>>qq;
		for(int i=1;i<=n;i++) cin>>a[i],q[i].clear();
		tt.build(-n,n,1),tr.build(1,n,1);
		for(int i=1;i<k;i++) tt.add(a[i]-i,-n,n,1,1);
		for(int i=k;i<=n;i++){
			tt.add(a[i]-i,-n,n,1,1);
			g[i]=k-tt.val[1];
			tt.add(a[i-k+1]-i+k-1,-n,n,1,-1);
		}
		for(int i=1,l,r;i<=qq;i++)cin>>l>>r,q[l+k-1].push_back({i,r});
		tp=st;
		*(tp++)={n+1,inf};
		for(int i=n;i>=k;i--){
			while(tp!=st&&tp[-1].val>=g[i]) tp--,tr.add(tp->pos,tp[-1].pos-1,1,n,1,g[i]-tp->val);
			*(tp++)={i,g[i]},tr.add(i,i,1,n,1,g[i]);
			for(auto j:q[i]) ans[j.t]=tr.query(i,j.r,1,n,1);
		}
		for(int i=1;i<=qq;i++) cout<<ans[i]<<'\n';
	}
}