这道题的主流做法是主席树。

考虑离线怎么做，首先是莫队，但是很明显莫队很难往在线扩展。那么考虑线段树。

首先进行一些分析，我们可以对于每个 \(a\)，将第 \(i\) 个 \(a\) 和第 \(i+k\) 个 \(a\) 配对，那么如果 \([l,r]\) 中包含了 \(k+s\) 个 \(a\)，则一共包含了 \(s\) 个对。那么 \(ans_{l,r}\) 就是区间长度 \(r-l+1\) 减去其包含的配对对数。

我们就可以在每个 \(r\) 上挂上询问，然后处理到 \(r\) 的时候，直接看 \([l,r]\) 的区间上有多少个左端点。因为右端点都不超过 \(r\)，所以左端点的个数就是被覆盖的答案的个数。

然后在线呢？这种静态离线形式一看就是主席树预处理暴力搞。逐个加入 \(a_i\)，对每个 \(a\) 维护一个队列，每次队列大小为 \(k\) 时从头部弹出和当前配对，然后加入第 \(i\) 个树。查询的时候就是在时间 \(r\) 的线段树上查找 \([l,r]\) 有多少个左端点即可。

我们考虑不用主席树，使用别的数据结构。树套树就是不错的选择。我们在每个线段树节点维护一个平衡树。对每个配对点 \(x,y\)，在所有覆盖 \(y\) 的区间上插入 \(x\)。然后查询的时候，找到所有被 \([l,r]\) 完全覆盖的最大区间，在每个区间上面的平衡树上查找有多少个位置大于等于 \(l\)，加和即可。

这里的内层平衡树能不能用 \(set\) 替代呢？很可惜不可以。因为我们要查找有多少个位置大于等于 \(l\)。但是静态，所以我们可以用 \(vector\)，在 \(vector\) 的所有元素维护好之后，就可以 \(lower\_bound\) 查询。

时间复杂度 \(O(n\log^2 n)\)，空间复杂度 \(O(n\log n)\)，但是没有用到高级数据结构。

struct node{
	int l,r;
	vt<int>v;
}sg[400005];
inline void init(int i,int l,int r){
	sg[i].l=l,sg[i].r=r;sg[i].v.clear();
	if(l==r)return;
	init(i<<1,l,l+r>>1);
	init(i<<1|1,(l+r>>1)+1,r);
}
inline void add(int i,int x,int v){
	if(sg[i].l>x||sg[i].r<x)return;
	sg[i].v.pb(v);
	if(sg[i].l==sg[i].r)return;
	add(i<<1,x,v);
	add(i<<1|1,x,v);
}
inline void flush(int i){
	sort(sg[i].v.begin(),sg[i].v.end());
	if(sg[i].l==sg[i].r)return;
	flush(i<<1);
	flush(i<<1|1);
}
inline int qry(int i,int l,int r){
	if(sg[i].l>r||sg[i].r<l)return 0;
	if(sg[i].l>=l&&sg[i].r<=r){
		vt<int>&v=sg[i].v;
		int x=lower_bound(v.begin(),v.end(),l)-v.begin();
		return v.size()-x;
	}
	return qry(i<<1,l,r)+qry(i<<1|1,l,r);
}
int n,a[100005],k,Q,l,r,ans;
queue<int>q[100005];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	rp(i,n)cin>>a[i];
	init(1,1,n);
	rp(i,n){
		if(q[a[i]].size()==k){
			add(1,i,q[a[i]].front());
			q[a[i]].pop();
		}q[a[i]].push(i);
	}
	flush(1);
	cin>>Q;
	rd(_,Q){
		cin>>l>>r;
		l=(l+ans)%n+1;
		r=(r+ans)%n+1;
		if(l>r)swap(l,r);
		ans=r-l+1-qry(1,l,r);
		cout<<ans<<'\n';
	}
	return 0;
}
//Crayan_r