|Educational Codeforces Round 22|
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.
1 1 1 2 2 2
In the first example the real plans are: