D. Несекретный шифр
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Берляндия в ходе войны с Флатландией начинает перехватывать инициативу. Чтобы изгнать противника с родной земли, берляндцам нужно точно знать, сколько еще флатландских солдат осталось в резерве врага. К счастью, утром разведчики взяли «языка», у которого было секретное зашифрованное сообщение с нужной берляндцам информацией.

У пойманного нашли массив целых положительных чисел. Берляндская разведка уже давно знает шифр флатландцев: чтобы передать сообщение, в котором фигурирует число m, враги используют такой массив чисел a, что количество его подмассивов, в которых есть хотя бы k одинаковых чисел, равно m. Число k давно известно всей берляндской армии, поэтому генерал Туристов снова попросил ефрейтора Васю выполнить несложное задание: расшифровать сообщение флатландцев.

Помогите Васе, по заданному массиву чисел a и числу k, найдите количество подмассивов массива чисел a, в которых есть хотя бы k одинаковых чисел.

Подмассивом a[i... j] (1 ≤ i ≤ j ≤ n) массива a = (a1, a2, ..., an) называется массив, составленный из последовательных его элементов, начиная с i-го и заканчивая j-м: a[i... j] = (ai, ai + 1, ..., aj).

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

В первой строке через пробел записаны два целых числа n, k (1 ≤ k ≤ n ≤ 4·105) — количество чисел в массиве и требуемое количество одинаковых чисел в подмассивах, соответственно.

Во второй строке через пробел записаны n целых чисел ai (1 ≤ ai ≤ 109) — элементы массива.

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

Выведите единственное число — количество подмассивов массива a таких, что в них есть как минимум k одинаковых чисел.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
4 2
1 2 1 2
Выходные данные
3
Входные данные
5 3
1 2 1 1 3
Выходные данные
2
Входные данные
3 1
1 1 1
Выходные данные
6
Примечание

В первом примере существует три подмассива, содержащих хотя бы два одинаковых числа: (1,2,1), (2,1,2) и (1,2,1,2).

Во втором примере существует два подмассива, содержащих три одинаковых числа: (1,2,1,1,3) и (1,2,1,1).

В третьем примере любой подмассив содержит хотя бы 1 число. Всего их 6: (1), (1), (1), (1,1), (1,1) и (1,1,1).