F. НСП?
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Став старшеклассником, 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$$$.

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

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

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

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

Выведите одно целое число — минимальное количество операций.

Примеры
Входные данные
5
1 2 3 4 5
Выходные данные
6
Входные данные
6
-1 -5 -4 -1 -4 -7
Выходные данные
0
Входные данные
11
0 1000000 1 -50000 2 998353 3 -100007 4 200943 0
Выходные данные
1936973
Примечание

В первом примере вы можете выполнить операции на подотрезках $$$[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$$$. Поэтому вам не нужно выполнять никаких операций.