← 返回题目列表

Codeforces · 1982/C

C. 无聊的一天

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

又是无聊的一天,叶戈尔觉得无聊,决定做点什么。但由于他没有朋友,他想出了一个游戏来玩。

Egor 有一副 $$$n$$$ 牌,从顶部开始的 $$$i$$$ 牌上写着数字 $$$a_i$$$。叶戈尔想玩一定数量的回合,直到牌用完。在每一轮中,他从牌堆顶部取出非零数量的牌并完成该轮。如果本轮中收集到的卡片上的数字总和在 $$$l$$$ 和 $$$r$$$(含)之间,则该轮获胜;否则,它就会丢失。

叶戈尔牢记纸牌的顺序。帮助叶戈尔确定他在这样的游戏中可以赢得的最大回合数。请注意,叶戈尔不需要连续赢得回合。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \le n \le 10^{5}$$$、$$$1 \le l \le r \le 10^9$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 卡片上从上到下的数字。

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

输出

对于每个测试用例,输出一个数字 - Egor 可以获胜的最大回合数。

示例

输入 #1

8
5 3 10
2 1 11 3 7
10 1 5
17 8 12 11 7 11 21 13 10 8
3 4 5
3 4 2
8 12 25
10 7 5 13 8 9 12 7
2 3 3
5 2
9 7 9
2 10 5 1 3 7 6 2 3
1 8 10
9
5 5 6
1 4 2 6 4

输出 #1

3
0
1
4
0
3
1
2

注意

在第一个测试用例中,Egor 可以赢得 $$$3$$$ 轮:

- 在第一轮中,拿走价值 $$$2$$$ 和 $$$1$$$ 的顶部 $$$2$$$ 牌并获胜,因为它们的总和为 $$$3$$$。之后,牌组将如下所示:$$$[11, 3, 7]$$$。
- 在第二轮中,拿走最上面的牌并输,因为它的价值 $$$11$$$ 大于 $$$r = 10$$$。之后,牌组将如下所示:$$$[3, 7]$$$。
- 在第三轮中,拿走价值 $$$3$$$ 的顶牌并获胜。之后,牌组将如下所示:$$$[7]$$$。
- 此后,在第四轮中,叶戈尔只需拿走牌组中最后一张价值 $$$7$$$ 的牌即可再次获胜。

在第二个测试用例中,Egor 无法赢得任何回合,无论他如何努力。

在第三个测试用例中,每轮可以拿一张牌,那么第一轮和第三轮都会输,第二轮就会赢。

在第四个测试用例中,您可以在每轮中拿两张牌并且总是获胜。