E. Разделение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Фермера Джона есть массив $$$a$$$, содержащий $$$n$$$ положительных целых чисел и целое число $$$k$$$.

Пусть $$$a[l, r]$$$ будет подмассивом$$$^{\text{∗}}$$$ массива $$$a$$$. Он выполняет следующую процедуру, чтобы независимо определить, является ли подмассив $$$a[l, r]$$$ потрясающим:

  • Изначально у ФД $$$k$$$ пустых мультимножеств, пронумерованных от $$$1$$$ до $$$k$$$.
  • Затем, для каждого элемента $$$a_i$$$ ($$$1 \leq i \leq n$$$) в массиве $$$a$$$:
    • Если $$$l\leq i\leq r$$$ (то есть $$$a_i$$$ находится в подмассиве $$$a[l, r]$$$), он помещает $$$a_i$$$ в мультимножество $$$1$$$,
    • В противном случае он помещает $$$a_i$$$ в любое мультимножество, которое он хочет (это может быть мультимножество $$$1$$$).
  • Подмассив $$$a[l, r]$$$ является потрясающим, если существует способ разместить элементы так, чтобы для каждого значения $$$v$$$ все мультимножества содержали одинаковое количество элементов со значением $$$v$$$. Другими словами, он хочет сделать так, чтобы все мультимножества содержали одни и те же элементы (игнорируя порядок).

Выведите количество потрясающих подмассивов.

$$$^{\text{∗}}$$$Для массива $$$a$$$ размером $$$n$$$ и целых чисел $$$1\leq l\leq r\leq n$$$, подмассив $$$a[l, r]$$$ обозначает массив, состоящий из элементов $$$a_l, \ldots, a_r$$$, в порядке.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq k \le n \leq 2 \cdot 10^5$$$).

Следующая строка содержит $$$n$$$ целых чисел, разделенных пробелом: $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число на новой строке: количество потрясающих подмассивов.

Пример
Входные данные
4
3 2
1 1 1
4 2
1 2 1 2
8 2
3 3 3 3 2 2 2 2
6 3
1 1 1 1 1 1
Выходные данные
0
7
18
11
Примечание

Набор входных данных 1: $$$n=3$$$, $$$a=[1,1,1]$$$.

Для $$$k=2$$$ вы не можете закончить с одинаковым количеством $$$1$$$ в обоих мультимножествах, поэтому ни один подмассив не подходит.

Набор входных данных 2: $$$n=4$$$, $$$a=[1,2,1,2]$$$.

Для $$$k=2$$$ конечное состояние должно дать каждому мультимножеству ровно одну $$$1$$$ и одну $$$2$$$. Таким образом, подходящий подмассив может содержать не более одной $$$1$$$ и не более одной $$$2$$$.