E. Min-Sum-Max
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Tom ожидает результатов экзамена. Чтобы разрядить напряженную обстановку, его друг Daniel решил сыграть с ним в игру. Игра называется «Раздели массив».

В игре есть массив $$$a$$$, состоящих из $$$n$$$ целых чисел. Обозначим $$$[l,r]$$$ как подотрезок, состоящий из целых чисел $$$a_l,a_{l+1},\ldots,a_r$$$.

Tom разобьет массив на подряд идущие подотрезки $$$[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$$$, такие, что каждое число находится ровно в одном подотрезке. Более формально:

  • Для всех $$$1\le i\le m$$$, $$$1\le l_i\le r_i\le n$$$;
  • $$$l_1=1$$$, $$$r_m=n$$$;
  • Для всех $$$1< i\le m$$$, $$$l_i=r_{i-1}+1$$$.

Обозначим $$$s_{i}=\sum_{k=l_i}^{r_i} a_k$$$, то есть $$$s_i$$$ — сумма целых чисел в $$$i$$$-м подотрезке. Для всех $$$1\le i\le j\le m$$$ должно выполняться следующее условие:

$$$$$$ \min_{i\le k\le j} s_k \le \sum_{k=i}^j s_k \le \max_{i\le k\le j} s_k. $$$$$$

Tom считает, что чем на большее количество подотрезков будет разбит массив $$$a$$$, тем лучший результат он получит. Поэтому он просит Daniel найти максимальное количество подотрезков среди всех возможных способов разделить массив $$$a$$$. Вы должны помочь ему найти это число.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1\le t\le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 300$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

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

Для каждого набора входных данных выведите одно целое число — максимальное количество подотрезков среди всех возможных способов разделить массив $$$a$$$.

Пример
Входные данные
8
3
-1 5 4
2
2023 2043
6
1 4 7 -1 5 -4
5
-4 0 3 -18 10
1
998244853
10
-4 2 5 -10 4 8 2 9 -15 7
7
-7 3 8 -9 -2 2 4
4
-5 5 -2 -5
Выходные данные
2
1
3
2
1
6
5
3
Примечание

В первом наборе входных данных Daniel может разделить массив на $$$[-1]$$$ и $$$[5,4]$$$, и $$$s=[-1,9]$$$. Можно видеть, что при любых $$$i=j$$$, условие выполняется, и для $$$i=1,j=2$$$, мы имеем $$$\min(-1,9)\le (-1)+9\le \max(-1,9)$$$.

Во втором наборе входных данных, если Daniel разделит массив на $$$[2023]$$$ и $$$[2043]$$$, то для $$$i=1,j=2$$$ мы имеем $$$2023+2043>\max(2023,2043)$$$, поэтому максимальное количество подотрезков равно $$$1$$$.

В третьем наборе входных данных оптимальным способом разделить массив является $$$[1,4,7],[-1],[5,-4]$$$.

В четвёртом наборе входных данных оптимальным способом разделить массив является $$$[-4,0,3,-18],[10]$$$.

В пятом наборе входных данных Daniel может получить только один подотрезок.