题目描述

在 Deepwoken 的世界里，存在一件远古神器——无限知识石板，上面刻着长度为 $n$ 的神秘符号序列（每个符号是一个整数）。

传说要发现神器的真正力量，需要找出所有神圣片段——即连续区间，其包含恰好 $k$ 个不同的数，且长度在 $l$ 到 $r$（含）之间。

形式化描述：给定序列 $a$（长度为 $n$）以及整数 $k,l,r$，统计满足以下条件的区间端点 $b,c$ 的数量：

• $1\le b\le c\le n$；
• 子数组 $[a_b,a_{b+1},\dots,a_c]$ 中恰好包含 $k$ 个不同的数；
• $l\le c-b+1\le r$。

输入格式

• 第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例数。

• 接下来描述 $t$ 个测试用例。每个测试用例包含两行：

  • 第一行包含四个整数 $n,k,l,r$，满足 $1\le k\le n\le 2\cdot 10^5$，$1\le l\le r\le n$。
  • 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，满足 $1\le a_i\le 10^9$。

数据保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数——满足条件的连续子数组的数量。

样例输入

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

样例输出

1
5
10
7
5

说明

样例解释

• 样例 $1$：$a=[5]$，只有子数组 $[5]$，长度 $1$ 且包含恰好 $1$ 个不同数，计数为 $1$。
• 样例 $4$：$a=[7,7,7,7]$，任一相同数的子数组都包含恰好 $1$ 个不同数，长度允许为 $1$ 或 $2$，共有 $4$ 个长度 $1$ 子数组与 $3$ 个长度 $2$ 子数组，共 $7$。
• 样例 $5$：$a=[1,2,1,2,3,2,1]$，列举符合 $k=3,l=2,r=4$ 的所有子数组后共有 $5$ 个。