保持高平均值

• 时间限制：1.5 秒
• 内存限制：256 MiB

题目描述

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

你需要选择尽可能多的数组元素，使得对于任意一个长度大于 $1$ 的连续子段 $a_l,a_{l+1},\ldots,a_r$，下列两个条件至少满足一个：

• 该子段中至少有一个元素未被选择；
• 该子段所有元素之和不小于 $x\cdot(r-l+1)$。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

接下来是 $t$ 组测试数据。每组数据包含三行：

• 第一行包含一个整数 $n$，表示数组长度；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$；
• 第三行包含一个整数 $x$。

输出格式

对于每组测试数据，输出一行一个整数，表示最多可以选择的元素个数。

样例输入 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

数据范围

对于所有数据，$1\le t\le10$，$1\le n\le50000$，$-100000\le a_i\le100000$，$-100000\le x\le100000$。

提示

在样例一中，可以不选择元素 $2$，并选择其余四个元素。不能选择所有元素，因为子段 $[1,2]$ 的元素和为 $3$，小于 $2\times2$。

在样例二中，可以选择所有值为 $4$ 的元素和首尾适当的值为 $2$ 的元素，共选择 $8$ 个。

在样例三中，可以选择两个值为 $-10$ 的元素；在样例四中，可以选择前两个值为 $9$ 的元素。