在世界上 深度觉醒,存在一件远古神器—— 无限知识平板,上面刻有一系列$$$n$$$神秘符号(每个符号都是一个整数)。
据说,只有找到所有物品才能揭示该神器的真正威力。 神圣碎片 — 包含精确 $$$k$$$ 不同数字的平板电脑的连续段,其长度必须在 $$$l$$$ 和 $$$r$$$ 之间(包含)。
形式上:给定一个长度为 $$$n$$$ 的序列 $$$a$$$ 和整数 $$$k$$$、$$$l$$$、$$$r$$$。您需要找到此类边界 $$$b$$$ 和 $$$c$$$ 的数量,以便:
- $$$1 \le b \le c \le n$$$;
- 在元素 [$$$a_{b}, a_{b + 1}, \dots, a_{c}$$$] 中,正好有 $$$k$$$ 不同的数字;
- $$$l \leq c - b + 1 \leq r$$$。
输入
每个测试由多个测试用例组成。
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
下面介绍测试用例。
每个测试用例的第一行包含四个整数:$$$n$$$、$$$k$$$、$$$l$$$ 和 $$$r$$$ $$$( 1 \le k \le n \le 2 \cdot 10^5, 1 \le l \le r \le n)$$$。
第二行包含 $$$n$$$ 数字 $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — 神秘符号。
保证所有测试用例的 $$$n$$$ 总价值不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试,在单独的行上输出一个整数 - 满足指定条件的连续子数组的数量。
示例
输入复制
51 1 1 155 2 2 31 2 1 3 26 3 1 61 2 3 1 2 34 1 1 27 7 7 77 3 2 41 2 1 2 3 2 1
输出复制
151075
注意
在第一个测试用例$$$a=[5]$$$中,只有一个子数组$$$[5]$$$,其长度为1并且恰好包含$$$1$$$不同的数字。
在第四个测试用例 $$$a=[7,7,7,7]$$$ 中,任何相同数字的子数组都给出精确的 $$$1$$$ 不同数字。可能的子数组的开头和结尾是:
- 长度$$$1$$$:$$$[1,1]$$$、$$$[2,2]$$$、$$$[3,3]$$$、$$$[4,4]$$$。
- 长度$$$2$$$:$$$[1,2]$$$、$$$[2,3]$$$、$$$[3,4]$$$。
在第五个测试用例 $$$a=[1,2,1,2,3,2,1]$$$ 中:
- 长度 $$$2$$$:所有子数组只有 $$$2$$$ 不同的数字。
- 长度$$$3$$$:$$$[3,5]$$$,$$$[5,7]$$$。
- 长度$$$4$$$:$$$[2,5]$$$、$$$[3,6]$$$、$$$[4,7]$$$。