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

Limits: 2 sec., 512 MiB

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

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

— Що сталося?

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

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

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

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

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

Input

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

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

Output

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

Constraints

\(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 балів: без додаткових обмежень.

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

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 1 2 2 3 4 1 2	8

Input (stdin) сopy	Output (stdout) сopy
4 1 4 7 4 7	10

Input (stdin) сopy	Output (stdout) сopy
4 2 4 4 4 4	0

Notes

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