这道题的主流做法是主席树。
考虑离线怎么做，首先是莫队，但是很明显莫队很难往在线扩展。那么考虑线段树。
首先进行一些分析，我们可以对于每个 \(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