Став старшеклассником, Tom увлекся задачами о массивах, причем не только задачей о наибольшей возрастающей подпоследовательности, но и задачей о наибольшей сумме на подотрезке. Он получил от своего друга Daniel очень интересную задачу. Однако ему кажется, что она очень сложная, поэтому он просит вас помочь.
Дан массив \(a\), состоящий из \(n\) целых чисел.
За одну операцию нужно сделать следующее:
- Выбрать подотрезок \([l,r]\) (\(1\le l\le r\le n\)) такой, что сумма на этом подотрезке наибольшая среди всех подотрезков в массиве \(a\). Более формально, \(\displaystyle\sum_{i=l}^r a_i=\max_{1\le l'\le r'\le n}\sum_{i=l'}^{r'} a_i\).
- Затем вычесть \(1\) из всех элементов \(a_l,a_{l+1},\ldots,a_r\).
Найдите минимальное количество операций, которые нужно выполнить, чтобы сделать \(a_i<0\) для всех \(1\le i\le n\).
Выходные данные
Выведите одно целое число — минимальное количество операций.
Примечание
В первом примере вы можете выполнить операции на подотрезках \([1,5],[1,5],[2,5],[3,5],[4,5],[5,5]\) в таком порядке. Ещё вы можете выполнить операции на подотрезках \([1,5],[2,5],[3,5],[4,5],[5,5],[1,5]\) в таком порядке.
Во втором примере уже выполнено условие \(a_i<0\) для всех \(1\le i\le n\). Поэтому вам не нужно выполнять никаких операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 5
|
6
|
|
2
|
6
-1 -5 -4 -1 -4 -7
|
0
|
|
3
|
11
0 1000000 1 -50000 2 998353 3 -100007 4 200943 0
|
1936973
|