CF813E Army Creation

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; $ i $ th 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. $ i $ th 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.

N/A

N/A

In the first example the real plans are: 1. $ 1 2 $ 2. $ 1 6 $ 3. $ 6 6 $ 4. $ 2 4 $ 5. $ 4 6 $