【普及】求和游戏

给你一个长度为 $n$ 的数组 $a$ 和 $2$ 个整数 $l, r(l \le r)$，游戏规则如下：

• 1、每一轮你可以从数组的左边开始，连续拿走若干个数
• 2、如果拿走的这些数的和在 $l$ 到 $r$ 之间，你可以获得 $1$ 分，否则不能得分

你可以进行多轮游戏，直到数组为空；请问你最多可以获得多少分？

输入格式

第一行包含 $1$ 个整数 $T$，表示数据组数

每组数据的第一行包含 $3$ 个整数 $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 \times 10^5$

输出格式

对于每组数据输出 $1$ 行包含 $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

3
0
1
4
0
3
1
2

2
3 4 5
3 3 1
3 4 5
3 3 4

1
1

提示

【样例 1 解释】

在第一个测试案例中，你可以获得 $3$ 分：

• 在第一轮中，取牌值为 $[2, 1]$，它们的总和是 $3(3 \le 3 \le 10)$，你可以获得 $1$ 分，数组会变成：$[11,3,7]$
• 第二轮，取 $[11]$，无法得分，因为其和为 $11>10$，数组会变成：$[3,7]$
• 第三轮，取 $[3]$，你可以获得 $1$ 分，因为其和为 $3\le 3 \le 10$，数组会变成：$[7]$
• 第四轮，取 $[7]$，你可以获得 $1$ 分，因为其和为 $3\le 7 \le 10$，数组被取空
• 所以你能获得 $3$ 分

【数据范围】

• $1 \le T \le 10^{4}$
• $1 \le n \le 10^{5}$
• $1 \le l \le r \le 10^9$
• $1 \le a_i \le 10^9$
• 保证所有数据的 $n$ 之和不超过 $2 \times 10^5$

来源

• 参考答案