ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Отборочный турнир сезона «Весна — 2023» > задача:


H. Макс и формирование букета

Отборочный турнир сезона «Весна — 2023»

Старт: 06.мая.2023 в 10:00:00
Финиш: 14.мая.2023 в 23:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• A. Макс и термометр
• B. Макс и ключ
• C. Макс и ДНК
• D. Макс и объединение результатов
• E. Макс и дни рождения великих
• F. Макс и аттракционы
• G. Макс и математические часы
• H. Макс и формирование букета
• I. Макс и номера телефонов
• J. Макс и кубик Рубика 2x2x2

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и формирование букета
Макс и формирование букета
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Максу срочно понадобилось купить красивый букет цветов. В цветочном магазине Макс увидел $$$N$$$ цветов, стоящих в ряд, из которых можно собрать букет.

Флорист, работающий в магазине, подсказал Максу, что букет получится красивым, если будут выполнены два условия:

  • Цветы, из которых формируется букет, должны составлять непрерывный подотрезок ряда;
  • В букете должно быть ровно $$$K$$$ различных видов цветов.

Помогите Максу определить, сколько существует способов составить из цветов красивый букет.

Входные данные

Первая строка содержит целые числа $$$N$$$ и $$$K$$$ ($$$1 \le K \le N \le 3 \cdot 10^5$$$) — соответственно количество цветов в ряду и количество различных видов цветов, которые должны быть в красивом букете.

Вторая строка содержит $$$N$$$ целых чисел $$$A_i$$$ ($$$1 \le A_i \le 10^9$$$) — виды каждого из цветов в ряду.

Выходные данные

Выведите одно целое число — количество способов сформировать красивый букет.

Примеры

Входные данные
8 2
1 2 1 2 1 3 1 2
Выходные данные
14
Входные данные
8 3
1 2 1 2 1 3 1 2
Выходные данные
14

Для отправки решений необходимо выполнить вход.

www.contester.ru