Задача . Balancing Bacteria

У Фермера Джона \(N\) (\(1\le N\le 2\cdot 10^5\)) участков травы на прямой, где участок \(i\) имеет уровень бактерий, который отличается на \(a_i\) от здоровой травы (\(-10^{15}\le a_i \le 10^{15}\)). Например, если \(a_i = -3\), тогда кусок \(i\) имеет уровень бактерий на 3 меньше, чем нормальный. И нужно прибавить ровно 3 дополнительных единицы бактерий, чтобы уровень бактерий в этом куске рассматривался как нормальный.

ФД хочет обеспечить, чтобы каждый кусок травы был скорректирован, чтобы получить нормальные уровни бактерий на них. У него есть два вида пестицидов, один добавляет бактерии, другой удаляет бактерии. ФД распространяет любой из двух видов пестицидов, стоя в куске \(N\) (самом правом куске) и выбирает уровень мощности \(L\) (\(1 \leq L \leq N\)).

Сила действия спрейера уменьшается по мере увеличения расстояния от него. Например, если фермер выберет пестицид, который добавляет бактерии, тогда \(L\) единиц бактерий в участок \(N\), \(L-1\) единиц бактерий в участок \(N-1\), \(L-2\) единицы бактерий в участок \(N-2\) и т.д. Участки \(1 \ldots N-L\) не получат бактерий, поскольку мощность спрейера недостаточна, чтобы их достать. Аналогично, если ФД выберет пестициды, которые удаляют бактерии, тогда \(L\) единиц бактерий будет удалено с участка \(N\), \(L-1\) единиц бактерий будет удалено с участка \(N-1\) и т.д. Опять, участки \(1 \ldots N-L\) будут не изменены.

Определите минимальное количество раз, которое ФД должен применить свой спрейер так, чтобы на каждом участке стало рекомендованное количество бактерийю Гарантируется, что ответ не превысит \(10^9\).

Может потребоваться использование 64-битного типа данных (например "long long" в C/C++)

6