← 返回题目列表

Codeforces · 1840/C

C. 滑雪场

中文机器翻译题面 查看原题

Dima Vatrushin 是学校的数学老师。由于工作出色,他被安排休假 $$$n$$$ 天。迪马一直梦想着去滑雪场,所以他想连续抽出几天时间去滑雪。由于假期需要精心准备,所以他至少只会去 $$$k$$$ 天。

给你一个数组$$$a$$$,其中包含度假村的天气预报。也就是说,第 $$$i$$$ 天的温度将为 $$$a_i$$$ 度。

迪马出生在西伯利亚,所以只有整个假期期间气温不超过$$$q$$$度,他才能去度假。

不幸的是,迪马太专注于抽象代数,以至于忘记了如何计算。他要求你帮助他数一下在度假村选择度假日期的方式有多少种。

输入

输入的第一行包含一个整数 $$$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$$$,在度假村的最短天数,以及迪马的最高舒适温度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 滑雪场的温度。

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

输出

输出 $$$t$$$ 个整数,每个整数都是相应测试用例的答案 - Dima 选择度假村度假日期的方式数。

示例

输入 #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

输出 #1

6
0
1
0
0
1
9

注意

在示例的第一个测试用例中,Dima 可以在任何一天进行,因此适合他的日期是 [1], [2], [3], [1, 2], [2, 3], [1, 2, 3]。

在示例的第二个和第四个测试用例中,Dima 由于高温而无法在任何一天进行,因此没有合适的日期。

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