给定一个整数数组 $$$a_1、a_2、\ldots、a_n$$$ 和一个整数 $$$x$$$。
您需要选择数组中的最大元素数,以便对于每个子段 $$$a_l, a_{l + 1}, \ldots, a_r$$$ 严格包含多个元素 $$$(l < r)$$$,或者:
- 该子段上至少有一个元素未被选择,或者
- $$$a_l + a_{l+1} + \ldots + a_r \geq x \cdot (r - l + 1)$$$。
输入
第一行输入包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10$$$):测试用例的数量。
下面是 $$$t$$$ 测试用例的描述,每个测试用例三行。
在第一行中,您将获得一个整数 $$$n$$$ ($$$1 \leq n \leq 50\,000$$$):数组中整数的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-100\,000 \leq a_i \leq 100\,000$$$)。
第三行包含一个整数 $$$x$$$ ($$$-100\,000 \leq x \leq 100\,000$$$)。
输出
对于每个测试用例,打印一个整数:可以选择的最大元素数。
示例
输入 #1
4 5 1 2 3 4 5 2 10 2 4 2 4 2 4 2 4 2 4 3 3 -10 -5 -10 -8 3 9 9 -3 5
输出 #1
4 8 2 2
注意
在第一个示例中,选择元素的一种有效方法是 $$$[\underline{1}, 2, \underline{3}, \underline{4}, \underline{5}]$$$。所有子分段至少满足其中一项标准。例如,对于子段$$$l = 1$$$,$$$r = 2$$$,我们发现元素$$$2$$$未被选择,满足第一个标准。对于子段$$$l = 3$$$,$$$r = 5$$$,我们有$$$3 + 4 + 5 = 12 \ge 2 \cdot 3$$$,满足第二个标准。
我们无法选择所有元素,因为在这种情况下,对于 $$$l = 1$$$、$$$r = 2$$$,所有元素都被选择,并且我们有 $$$a_1 + a_2 = 3 < 2 \cdot 2$$$。因此,所选元素的最大数量为 $$$4$$$。
在第二个示例中,一个有效的解决方案是 $$$[\underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}]$$$。
在第三个示例中,一个有效的解决方案是 $$$[\underline{-10}, -5, \underline{-10}]$$$。
在第四个示例中,一个有效的解决方案是 $$$[\underline{9}, \underline{9}, -3]$$$。