顾影自怜

题目描述

生命中曾拥有过的所有灿烂，原来终究，都需要用寂寞来偿还。——加西亚·马尔克斯

你，一位孤独的探索者，对数组的神秘魔力充满了好奇心。在你的昔日旅途中，你听说了一个关于数组的传说：每个数组都隐藏着一种神秘的力量，只要数组的最大值出现的次数大于等于某个阈值 $k$，这个数组便会拥有 $1$ 的 “魔力值”，否则不拥有魔力值；而一个数组的 “魔力等级”，是其所有子数组的魔力值之和。 现今给定一个长度为 $n$ 的数组，你迫切地想知道这个数组的魔力等级是多少。

请回忆：子数组是指原数组中连续的一段元素组成的数组片段。例如，对于数组 $a = [3, 2, 1, 3, 2]$，易知 $[2, 1], [1, 3], [3, 2, 1]$ 都是其子数组，但是 $[3, 3], [1, 4]$ 不是其子数组。

输入格式

本题单个测试点可能含有多组数据。输入的第一行包含数据组数 $T (1≤ T ≤ 10^6)$。 对于每组数据： 第一行包含两个整数 $n$ 和 $k (1 ≤ k ≤ n ≤ 10^6)$，分别表示数组长度和阈值。 第二行包含 $n$ 个整数 $a_1, a_2, . . . , a_n (1 ≤ a_i ≤ n)$，表示给定数组。 保证所有数据 $n$ 的总和不超过 $10^6$。

输出格式

对于每组数据，在一行内输出一个整数，即给定数组的魔力等级。

样例 #1

样例输入 #1

2
5 2
1 3 3 2 2
4 3
1 4 2 1

样例输出 #1

7
0

提示

在第一个样例中，子数组 $[1, 3, 3], [1, 3, 3, 2], [1, 3, 3, 2, 2], [3, 3], [3, 3, 2], [3, 3, 2, 2], [2, 2]$ 的最大值出现次数不小于 $2$ 次，共有 $7$ 个魔力值为 $1$ 的子数组，因此，数组的魔力等级为 $7$。 在第二个样例中，没有任何一个子数组中的最大值出现不小于 $3$ 次，因此，数组的魔力等级为 $0$。