409854: GYM103810 C Фуршет

Владимир пригласил гостей на фуршет по поводу своей победы. На праздничном столе расставлен ряд из $$$N$$$ блюд $$$T_1, T_2, ..., T_N$$$, где $$$T_i$$$ обозначает тип $$$i$$$-го блюда.

Перед приходом гостей Владимир решил немного перекусить, для этого он выбрал один тип блюда и стал есть блюда только этого типа. Так как отсутствие нескольких блюд подряд на столе будет слишком заметно, Владимир ест только блюда, между которыми не менее $$$K$$$ других блюд.

Определите, какой тип блюд должен выбрать Владимир, чтобы съесть как можно больше блюд.

Первая строка ввода содержит два целых числа – количество блюд $$$N (1 \le N \le 100000)$$$ и минимальное пропускаемых количество блюд $$$K$$$ $$$(1 \le K \le 100)$$$.

Вторая строка содержит $$$N$$$ целых чисел $$$T_i$$$ – номера типов блюд.

Вывести два целых числа – номер типа блюда и количество съеденных блюд. Если несколько типов блюд обеспечивают максимум количества блюд, то выведите минимальный номер типа из них.

Подзадача 1 (40 баллов) $$$1 \le N \le 100, 1 \le T_i \le 100, K=1$$$ В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.

Подзадача 2 (30 баллов) $$$100 \le N \le 100000, 1 \le T_i \le 100000, K=1$$$ Необходимые подзадачи: 1. В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.

Подзадача 3 (30 баллов) $$$100 \le N \le 100000, 1 \le T_i \le 10^9, 2 \le K \le 100$$$ Необходимые подзадачи: 1, 2. В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.

5 1
1 2 2 1 2

1 2

Пояснение к примеру 1: Владимир может съесть блюда с №1,4 (тип 1) или блюда с №2,5 (тип 2) или блюда с №3,5 (тип 2). Так как количество блюд во всех случаях равно 2, то выводим наименьший номер типа - 1.

Пояснение к примеру 2: Владимир может съесть блюда с №1,3,5 (тип 1).