Берляндия в ходе войны с Флатландией начинает перехватывать инициативу. Чтобы изгнать противника с родной земли, берляндцам нужно точно знать, сколько еще флатландских солдат осталось в резерве врага. К счастью, утром разведчики взяли «языка», у которого было секретное зашифрованное сообщение с нужной берляндцам информацией.
У пойманного нашли массив целых положительных чисел. Берляндская разведка уже давно знает шифр флатландцев: чтобы передать сообщение, в котором фигурирует число 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).
Выходные данные
Выведите единственное число — количество подмассивов массива a таких, что в них есть как минимум k одинаковых чисел.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере существует три подмассива, содержащих хотя бы два одинаковых числа: (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).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 2 1 2
|
3
|
|
2
|
5 3
1 2 1 1 3
|
2
|
|
3
|
3 1
1 1 1
|
6
|