给定一个整数数组 $$$a_1、a_2、\ldots、a_n$$$ 和两个整数 $$$s$$$ 和 $$$x$$$。计算数组中元素总和等于 $$$s$$$ 且最大值等于 $$$x$$$ 的子段数。
更正式地,计算对 $$$1 \leq l \leq r \leq n$$$ 的数量,使得:
- $$$a_l + a_{l + 1} + \ldots + a_r = s$$$。
- $$$\max(a_l, a_{l + 1}, \ldots, a_r) = x$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$s$$$ 和 $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$-2 \cdot 10^{14} \leq s \leq 2 \cdot 10^{14}$$$, $$$-10^9 \leq x \leq 10^9$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出元素总和等于 $$$s$$$ 且最大值等于 $$$x$$$ 的数组子段数。
示例
输入复制
91 0 001 -2 -1-23 -1 -1-1 1 -16 -3 -2-1 -1 -1 -2 -1 -18 3 22 2 -1 -2 3 -1 2 29 6 31 2 3 1 2 3 1 2 313 7 30 -1 3 3 3 -2 1 2 2 3 -1 0 32 -2 -1-2 -12 -2 -1-1 -2
输出复制
1 0 2 0 2 7 8 0 0
注意
在第一个测试用例中,合适的子段是 $$$l = 1$$$, $$$r = 1$$$。
在第三个测试用例中,合适的子段是 $$$l = 1$$$、$$$r = 1$$$ 和 $$$l = 3$$$、$$$r = 3$$$。
在第五个测试用例中,合适的子段是 $$$l = 1$$$、$$$r = 3$$$ 和 $$$l = 6$$$、$$$r = 8$$$。
在第六个测试用例中,合适的子段是 $$$r = l + 2$$$ 的子段。
在第七个测试用例中,以下子段是合适的:
- $$$l = 1$$$,$$$r = 7$$$。
- $$$l = 2$$$,$$$r = 7$$$。
- $$$l = 3$$$,$$$r = 6$$$。
- $$$l = 4$$$,$$$r = 8$$$。
- $$$l = 7$$$,$$$r = 11$$$。
- $$$l = 7$$$,$$$r = 12$$$。
- $$$l = 8$$$,$$$r = 10$$$。
- $$$l = 9$$$,$$$r = 13$$$。