Екстрене завдання

Обмеження: 2 сек., 512 МіБ

Після того як Зеник смачно пообідав, він отримав несподіваний дзвінок від своєї подруги Марічки. У її голосі відчувалося хвилювання:

— Зеник, виручай! У мене серйозна проблема.

— Що сталося?

— Я працюю аналітиком у компанії, що займається дослідженням унікальних послідовностей даних. Мій керівник поставив термінове завдання: знайти кількість підмасивів у масиві, де кількість унікальних чисел є не меншою за \(k\). Якщо я не впораюсь до кінця дня, мене можуть звільнити!

— Спокійно, Марічко. Поясни мені детальніше.

— У мене є масив з \(n\) цілих чисел. Потрібно знайти кількість підмасивів, де кількість унікальних елементів є не меншою за \(k\). Підмасив — це безперервна послідовність елементів у масиві. Два підмасиви вважатимемо різними, якщо відрізняються індекси їх початків або кінців.

Зеник швидко обдумав задачу. Для нього це була чергова головоломка, яку він вирішував замість кросвордів. Але цього разу ставка була занадто високою — робота Марічки!

Чи зможете ви допомогти Зенику врятувати подругу від звільнення?

Вхідні дані

У першому рядку задано два цілі числа \(n\) та \(k\) — розмір масиву та мінімальна кількість унікальних елементів у підмасиві.

У другому рядку задано \(n\) цілих чисел, розділених пробілами — масив \(a_i\).

Вихідні дані

Виведіть кількість підмасивів заданого масиву, у яких унікальних елементів є хоча б \(k\).

Обмеження

\(1 \leq k \leq n \leq 2 \cdot 10^5\),

\(1 \leq a_i \leq 10^9\).

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 10 балів: \(n \le 100\),

• 20 балів: \(n \le 1000\),

• 7 балів: \(k=1, n \le 1000\),

• 13 балів: \(k=1\),

• 47 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 1 2 2 3 4 1 2	8

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 4 7 4 7	10

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 2 4 4 4 4	0

Примітки

У першому прикладі [2, 2, 3, 4, 1] є підмасивом оригінального масиву і кількість унікальних елементів рівна 4. Всього є 8 таких підмасивів.