Army Creation

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有 $n$ 名战士，第 $i$ 名战士的类型为 $a_i$。对于每个询问，只能从指定编号区间中选择战士；为了使军队保持平衡，每种类型至多选择 $k$ 名战士。请计算最多能选择多少名战士。

询问经过上一次答案加密。令上一次询问的答案为 $last$，初始时 $last=0$。读入 $x,y$ 后，按下式还原真实区间：

若 $l>r$，则交换 $l,r$。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各战士的类型。

第三行包含一个整数 $q$。

接下来 $q$ 行，每行包含两个整数 $x,y$，表示一个加密后的询问。

输出格式

对于每个询问输出一行一个整数，表示平衡军队的最大人数。

样例输入

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

样例输出

2
4
1
3
2

数据范围

对于全部数据，$1\le n,k,q\le10^5$，$1\le a_i\le10^5$，$1\le x,y\le n$。

所有测试点均独立计分且分值相同。