题目描述

有一个含有 $n$ 个数的序列 $A$。共有 $q$ 次询问，每次询问 $[l,r]$ 内最多可以选多少个数，满足同一个数的出现次数不超过 $k$？

输入格式

第一行两个整数 $n,k$，$1\le n,k\le 10^5$。

第二行 $n$ 个整数 $a_i$，$1\le a_i\le 10^5$。

第三行一个整数 $q$，$1\le q\le 10^5$。

接下来 $q$ 行，每行两个整数 $x_i,y_i$。

此题强制在线，初始 $last = 0$，接下来每次询问前，$last$ 为上一次的答案：

1. $l_{i}=((x_{i}+last) \mod n)+1$；
2. $r_{i}=((y_{i}+last) \mod n)+1$；
3. 如果 $l_{i}>r_{i}$，交换 $l_{i}$ 与 $r_{i}$。

输出格式

对于每次询问，在一行中输出一个整数表示答案。

6 2
1 1 1 2 2 2
5
1 6
4 3
1 1
2 6
2 6

2
4
1
3
2