Как вы можете помнить из наших предыдущих контестов, Вова очень любит играть в компьютерные игры. Сейчас он играет в стратегию Rage of Empires.
В игре Вове доступны для найма n различных воинов; i-й воин имеет тип ai. Вова хочет создать сбалансированную армию, наняв какое-то подмножество воинов. Армия называется сбалансированной, если в ней присутствует не более k воинов одного типа. Конечно же, Вова хочет, чтобы его армия была как можно больше.
Но всё не так просто — Вове придётся рассмотреть q различных планов создания армии. i-й план позволяет ему нанимать только тех воинов, чей номер не меньше li и не больше ri.
Помогите Вове определить максимальный размер сбалансированной армии для каждого плана.
Обратите внимание, что параметры каждого плана заданы в изменённом виде. Подробнее в описании входных данных.
Выходные данные
Выведите q чисел. i-е число должно быть равно максимальному размеру сбалансированной армии при рассмотрении i-го плана.
Примечание
В первом примере планы создания армии следующие:
- 1 2
- 1 6
- 6 6
- 2 4
- 4 6
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
1 1 1 2 2 2
5
1 6
4 3
1 1
2 6
2 6
|
2
4
1
3
2
|