题目描述

在数据王国中，元素们按照某种神秘的规律排成一列。不同的元素代表着不同的能量属性，而连续的一段区间则蕴含着独特的组合力量。 魔法研究者们发现：当一个区间中恰好包含 $k$ 种不同的元素时，这个区间会产生一种稳定的结构，具有重要的研究价值。

给定一个长度为 $n$ 的整数数组 $A$，其中 $A_i$ 表示第 $i$ 个位置上的元素。 现在需要统计有多少个连续子段 $[L, R]$ 满足：

• 子段中的不同元素个数恰好为 $k$。

也就是说，对于每一个区间 $[L, R]$，设其中不同元素的个数为 $\text{distinct}(L, R)$，要求满足：

你需要对每组测试数据计算满足条件的子段数量。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。

接下来对于每组测试数据：

• 第一行包含两个正整数 $n, k$；
• 第二行包含 $n$ 个正整数 $A_1, A_2, \dots, A_n$。

输出格式

输出共 $T$ 行，每行一个整数，表示对应测试数据的答案。

样例 1 输入

5
1 1
5
5 2
1 2 1 3 2
6 3
1 2 3 1 2 3
4 1
7 7 7 7
7 3
1 2 1 2 3 2 1

样例 1 输出

1
5
10
10
11

样例 1 解释

以第二组数据为例：

数组为 $[1, 2, 1, 3, 2]$，$k = 2$。

满足恰好包含 $2$ 种不同元素的子段包括：

共计 $5$ 个。

样例 2

见选手目录下的 subsegment/subsegment2.in 和 subsegment/subsegment2.ans。

该测试用例满足测试点 $1 \sim 3$ 的约束条件。

数据范围

对于 $100\%$ 的数据，有 $1 \le T \le 10$ , $1 \le k \le n \le 10^6$ , $1 \le A_i \le 10^9$。

数据保证 $\sum n \le 10^6$，注意数据规模对输入效率造成的影响。

各测试点的附加限制如下表所示：

点击下载大样例