CF1616D.Keep the Average High

You are given an array of integers $a_1, a_2, \ldots, a_n$ and an integer $x$.

You need to select the maximum number of elements in the array, such that for every subsegment $a_l, a_{l + 1}, \ldots, a_r$ containing strictly more than one element $(l \lt r)$, either:

• At least one element on this subsegment is not selected, or
• $a_l + a_{l+1} + \ldots + a_r \geq x \cdot (r - l + 1)$.

给你一个整数数组 $a_1, a_2, \ldots, a_n$ 和一个整数 $x$。

你需要从该数组中选出尽可能多的元素，使得对任意包含严格多于一个元素的子段 $a_l, a_{l + 1}, \ldots, a_r$（即满足 $l \lt r$），以下两个条件中至少有一个成立：

• 该子段中至少有一个元素未被选中；或
• $a_l + a_{l+1} + \ldots + a_r \geq x \cdot (r - l + 1)$。

The first line of input contains one integer $t$ ($1 \leq t \leq 10$): the number of test cases.

The descriptions of $t$ test cases follow, three lines per test case.

In the first line you are given one integer $n$ ($1 \leq n \leq 50\,000$): the number of integers in the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-100\,000 \leq a_i \leq 100\,000$).

The third line contains one integer $x$ ($-100\,000 \leq x \leq 100\,000$).

输入的第一行包含一个整数 $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$）。

For each test case, print one integer: the maximum number of elements that you can select.

对于每个测试用例，输出一个整数：你能选择的元素的最大数量。

In the first example, one valid way to select the elements is $[\underline{1}, 2, \underline{3}, \underline{4}, \underline{5}]$. All subsegments satisfy at least one of the criteria. For example, for the subsegment $l = 1$, $r = 2$ we have that the element $2$ is not selected, satisfying the first criterion. For the subsegment $l = 3$, $r = 5$ we have $3 + 4 + 5 = 12 \ge 2 \cdot 3$, satisfying the second criterion.

We can't select all elements, because in this case for $l = 1$, $r = 2$ all elements are selected and we have $a_1 + a_2 = 3 \lt 2 \cdot 2$. Thus, the maximum number of selected elements is $4$.

In the second example, one valid solution is $[\underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}]$.

In the third example, one valid solution is $[\underline{-10}, -5, \underline{-10}]$.

In the fourth example, one valid solution is $[\underline{9}, \underline{9}, -3]$.

在第一个例子中，一种合法的元素选择方式是 $[\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 \lt 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]$。