박테리아 균형 맞추기

Farmer John은 일렬로 놓인 $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 단위 더 넣어야 한다.

Farmer John은 모든 조각을 건강한 수준으로 맞추려 한다. 박테리아를 추가하는 살충제와 제거하는 살충제, 두 종류가 있다. 어느 쪽을 뿌리든 그는 가장 오른쪽 조각 $N$에 서서 분무기의 세기 $L$ ($1 \leq L \leq N$)을 고른다.

분무기는 Farmer John에게 가까운 조각일수록 큰 영향을 주고, 멀어질수록 영향이 약해진다. 박테리아를 추가하는 살충제를 고르면 조각 $N$에 $L$ 단위, 조각 $N-1$에 $L-1$ 단위, 조각 $N-2$에 $L-2$ 단위가 더해지는 식이다. 분무기가 닿지 않는 조각 $1 \ldots N-L$에는 아무것도 더해지지 않는다. 박테리아를 제거하는 살충제도 같은 방식이지만, 더하는 대신 뺀다.

모든 조각이 건강한 박테리아 수준에 도달하도록, Farmer John이 살충제를 뿌려야 하는 최소 횟수를 구하라. 답은 최대 $10^9$임이 보장된다.

값이 매우 커질 수 있으므로 C/C++의 long long처럼 64비트 정수형을 사용해야 한다.

첫째 줄에 $N$이 주어진다.

둘째 줄에는 풀밭 각 조각의 초기 박테리아 수준을 나타내는 정수 $N$개 $a_1 \dots a_N$이 주어진다.

모든 조각의 박테리아 수준을 건강한 수준으로 맞추는 데 필요한 살충제 뿌리기의 최소 횟수를 출력한다.