题目描述

Dima Vatrushin 是一名学校的数学老师。由于工作出色，他被奖励了 $n$ 天的假期。Dima 长期以来一直梦想去滑雪胜地，因此他希望安排连续的几天去滑雪。由于度假需要精心准备，他只会选择至少 $k$ 天的假期。

给定一个数组 $a$，表示滑雪胜地的天气预报。也就是说，第 $i$ 天的温度为 $a_i$ 度。

Dima 出生在西伯利亚，所以只有当度假期间的温度始终不高于 $q$ 度时，他才会去度假。

不幸的是，Dima 太沉迷于抽象代数，已经忘记了如何计数。他请求你帮忙，计算他有多少种方式可以选择度假的日期。

输入格式

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

接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$k$、$q$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le n$，$-10^9 \le q \le 10^9$），分别表示数组 $a$ 的长度、在度假村的最少天数，以及 Dima 能接受的最高舒适温度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$），表示滑雪胜地每天的温度。

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

输出格式

输出 $t$ 个整数，每个整数表示对应测试用例中 Dima 可以选择度假日期的方案数。

说明/提示

在示例的第一个测试用例中，Dima 可以在任何一天去度假，因此适合他的日期有 [1]、[2]、[3]、[1, 2]、[2, 3]、[1, 2, 3]。

在示例的第二个和第四个测试用例中，由于温度过高，Dima 不能在任何一天去度假，因此没有适合的日期。

在示例的第三个测试用例中，Dima 只能选择日期 [1, 2, 3]。

由 ChatGPT 4.1 翻译

样例

7
3 1 15
-5 0 -10
5 3 -33
8 12 9 0 5
4 3 12
12 12 10 15
4 1 -5
0 -1 2 5
5 5 0
3 -1 4 -5 -3
1 1 5
5
6 1 3
0 3 -2 5 -4 -4

6
0
1
0
0
1
9