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\). Вы должны помочь ему найти это число.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество подотрезков среди всех возможных способов разделить массив \(a\).
Примечание
В первом наборе входных данных 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 может получить только один подотрезок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|