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

Разделы > Неотсортированные > задача:


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

Задачи раздела

• Макс и сонник
• Макс и степени двойки
• Макс и судоку
• Макс и судоку
• Макс и термометр
• Макс и тональности
• Макс и треугольник
• Макс и угол
• Макс и формирование букета
• Макс и электрички
• Макс и электронный дневник
• Макс и элитное жильё
• Макс, поезд и самолёт
• Максимальный элемент на отрезке
• Медиана
• Наименьшее общее кратное
• От 1 до N кратные K

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

Если у вас есть предложения или пожелания по работе 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