CF813E Army Creation

正如你可能还记得的，在之前的回合中，Vova 非常喜欢电脑游戏。现在，他正在玩一款名为 Rage of Empires 的策略游戏。 在游戏中，Vova 可以雇佣 $n$ 名不同的战士，第 $i$ 名战士的类型为 $a_i$。Vova 想要通过雇佣某些战士的子集，创建一支“平衡”的军队。如果对于游戏中出现的每种类型的战士，军队中这种类型的战士数量不超过 $k$，则这支军队被称为“平衡”的。当然，Vova 希望军队的规模尽可能大。 更复杂的是，Vova 需要考虑 $q$ 个不同的组建军队方案。第 $i$ 个方案只允许他雇佣编号不小于 $l_i$ 且不大于 $r_i$ 的战士。 请帮助 Vova，针对每个方案，确定平衡军队的最大可能人数。 需要注意的是，方案的输入形式经过了变换。具体见输入格式部分。

第一行包含两个整数 $n$ 和 $k$，满足 $1 \leq n, k \leq 100000$。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，满足 $1 \leq a_i \leq 100000$。 第三行包含一个整数 $q$，满足 $1 \leq q \leq 100000$。 接下来的 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个方案，满足 $1 \leq x_i, y_i \leq n$。 你需要记录上一个方案的输出结果（记作 $last$），开始时 $last=0$。若要还原第 $i$ 个方案 ($l_i, r_i$)，进行如下操作： 1. $l_i=((x_i+last) \bmod n)+1$； 2. $r_i=((y_i+last) \bmod n)+1$； 3. 若 $l_i>r_i$，交换 $l_i$ 和 $r_i$。

输出 $q$ 个整数，第 $i$ 个整数表示在考虑第 $i$ 个方案时，平衡军队的最大规模。

在第一个样例中，实际的查询方案为： 1. $1\ 2$ 2. $1\ 6$ 3. $6\ 6$ 4. $2\ 4$ 5. $4\ 6$ 由 ChatGPT 5 翻译