Пчеленок решил сделать Миле подарок. Пчеленок уже купил массив \(a\) длины \(n\), но дарить просто массив слишком банально. Вместо этого он решил подарить Миле подотрезки этого массива!
Пчеленок хочет, чтобы его подарок был красивым, поэтому он решил выбрать \(k\) непересекающихся подотрезков массива \([l_1,r_1]\), \([l_2,r_2]\), \(\ldots\) \([l_k,r_k]\) так, что:
- длина первого отрезка \([l_1,r_1]\) равна \(k\), длина второго отрезка \([l_2,r_2]\) равна \(k-1\), \(\ldots\), длина \(k\)-го отрезка \([l_k,r_k]\) равна \(1\)
- для любых \(i<j\) \(i\)-й подотрезок встречается в массиве раньше \(j\)-го (т.е. \(r_i<l_j\))
- суммы в этих подотрезках строго возрастают (т.е. пусть \(sum(l \ldots r) = \sum\limits_{i=l}^{r} a_i\) — сумма чисел на подотрезке массива \([l,r]\), тогда \(sum(l_1 \ldots r_1) < sum(l_2 \ldots r_2) < \ldots < sum(l_k \ldots r_k)\)).
Пчеленок также хочет, чтобы его подарок был как можно больше, поэтому он просит вас узнать, при каком максимальном \(k\) он сможет сделать подарок Миле!
Выходные данные
Для каждого набора входных данных выведите максимальное возможное значение \(k\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
1
3
1 2 3
5
1 1 2 2 3
7
1 2 1 1 3 2 6
5
9 6 7 9 7
|
1
1
2
3
1
|