D. Следи за большим средним
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$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$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число: максимальное количество элементов, которое вы можете выбрать.

Пример
Входные данные
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
Выходные данные
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]$$$.