You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

请兄长使用围棋规则获胜

题目背景

自从重岳一掌拍裂了望的棋盘，兄弟二人终于在棋道上达成了一项共识：

重岳不一定能解开望的棋局，但他确实能打开望的棋盘。

为避免双方对“破局”一词的理解再次出现分歧，望在新棋盘旁立了一张纸：

对弈须知：

1. 棋盘不是敌人。
2. 石桌不是敌人。
3. 弈友也不是敌人。
4. 对以上三条有异议，请先离开棋盘。

重岳读完，坐了下来。

“望，不必如此。”

望没有回答。他检查了一遍桌腿，又将棋盒移出了兄长的肘击范围。

棋过中盘，重岳陷入长考。

望神色平静。

重岳缓缓抬手。

望抱起棋盘。

重岳拿起茶杯。

望放下棋盘。

两人对视片刻。

“喝茶。”重岳说。

“请。”望说。

又过数手，重岳发现自己算漏了一处，抬手拍向额头。

望连棋盘带茶壶一起抱了起来。

“……拍我自己。”

望低头看了看怀里的东西，慢慢放回原处。

“兄长见谅。此局变化太多。”

重岳终于叹了口气。

“那便换个简单些的。”

望取出一些棋子，在桌上排成一列，另设了一道取舍题。

重岳仔细看完规则，问道：

“这次，总可以动手了？”

望将棋盘挪到身后。

“请兄长具体说明，准备动哪只手，动到哪里。”

题目描述

桌上按顺序排列着 $n$ 枚棋子，第 $i$ 枚棋子的势值为 $a_i$。

重岳可以取走任意数量的棋子，也可以一枚都不取。取走棋子后，原位置留空，其余棋子的位置不变。

给定一个整数 $x$，留下的棋子必须满足以下条件：

对于任意 $1 \le l < r \le n$，如果第 $l,l+1,\ldots,r$ 枚棋子全部留下，则必须有

也就是说，任何长度至少为 $2$、且棋子全部留下的连续区间，其平均势值都必须不小于 $x$。

请你求出，最多可以留下多少枚棋子。

注意：

• 条件适用于所有符合要求的连续区间，而不仅是某段连续棋子的整体。
• 单独一枚棋子不受平均势值限制，即使 $a_i<x$，也可以留下。
• 取走棋子不会使空位两侧的棋子变得相邻。例如，只留下第 $1,3$ 枚棋子时，不需要检查这两枚棋子的平均势值。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10$），表示测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $n$（$1 \le n \le 50000$），表示棋子的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^5 \le a_i \le 10^5$），表示每枚棋子的势值。

第三行包含一个整数 $x$（$-10^5 \le x \le 10^5$），表示平均势值的下限。

输出格式

对于每个测试用例，输出一行一个整数，表示最多可以留下的棋子数量。

样例

4
5
1 2 3 4 5
2
5
1 6 1 6 1
3
3
-10 -5 -10
-8
3
9 9 -3
5

4
4
2
2

样例说明

第一个测试用例中，可以取走第 $1$ 枚棋子，留下第 $2,3,4,5$ 枚棋子。

留下的棋子中，任意长度至少为 $2$ 的连续区间，其平均势值都不小于 $2$。

不能留下全部五枚棋子，因为第 $1,2$ 枚棋子的平均势值为 $1.5$，小于 $2$。

第二个测试用例中，可以取走第 $3$ 枚棋子，留下第 $1,2,4,5$ 枚棋子。

两段连续棋子分别为区间 $[1,2]$ 和 $[4,5]$，平均势值均为 $3.5$，满足要求。

不能留下全部五枚棋子。虽然整列棋子的平均势值等于 $3$，但第 $1,2,3$ 枚棋子的平均势值为 $\frac{8}{3}$，小于 $3$。

第三个测试用例中，可以取走第 $2$ 枚棋子，留下第 $1,3$ 枚棋子。

两枚棋子之间有空位，不构成连续区间；单独一枚棋子也不受平均势值限制，因此该方案合法。

第四个测试用例中，可以留下第 $1,2$ 枚棋子，取走第 $3$ 枚棋子，答案为 $2$。

重岳得出了答案。

望复核一遍，竟然一枚也不差。

“如何？”重岳问。

“兄长赢了。”

重岳笑了。

望也终于松开了一直护着桌角的手。

就在此时，重岳起身，准备活动一下肩膀。

望抱住棋盘，连退三步。

“小望。”

“兄长请讲。”

“已经下完了。”

“上次也没在下。”