As you might remember from our previous rounds, Vova really likes computer games. Now he is playing a strategy game known as Rage of Empires.
In the game Vova can hire n different warriors; ith warrior has the type a _{ i}. Vova wants to create a balanced army hiring some subset of warriors. An army is called balanced if for each type of warrior present in the game there are not more than k warriors of this type in the army. Of course, Vova wants his army to be as large as possible.
To make things more complicated, Vova has to consider q different plans of creating his army. ith plan allows him to hire only warriors whose numbers are not less than l _{ i} and not greater than r _{ i}.
Help Vova to determine the largest size of a balanced army for each plan.
Be aware that the plans are given in a modified way. See input section for details.
The first line contains two integers n and k (1 ≤ n, k ≤ 100000).
The second line contains n integers a _{1}, a _{2}, ... a _{ n} (1 ≤ a _{ i} ≤ 100000).
The third line contains one integer q (1 ≤ q ≤ 100000).
Then q lines follow. ith line contains two numbers x _{ i} and y _{ i} which represent ith plan (1 ≤ x _{ i}, y _{ i} ≤ n).
You have to keep track of the answer to the last plan (let's call it last). In the beginning last = 0. Then to restore values of l _{ i} and r _{ i} for the ith plan, you have to do the following:
Print q numbers. ith number must be equal to the maximum size of a balanced army when considering ith plan.
6 2
1 1 1 2 2 2
5
1 6
4 3
1 1
2 6
2 6
2
4
1
3
2
In the first example the real plans are:
Name |
---|