정올이는 일렬로 배열된 N (1 \leq N \leq 2 \cdot 10^5) 개의 풀밭을 가지고 있으며, 각 풀밭 i의 박테리아 수준은 건강한 풀과의 차이가 a_i입니다 (-10^{15} \leq a_i \leq 10^{15}). 예를 들어, a_i = -3이면, 풀밭 i는 정상보다 3 낮은 박테리아 수준을 가지고 있으며, 건강한 상태로 올리기 위해서는 정확히 3 단위의 박테리아가 추가되어야 합니다.

정올이는 모든 풀밭이 건강한 박테리아 수준을 갖도록 하고 싶습니다. 다행히도, 그는 필드에 두 가지 종류의 농약을 뿌릴 수 있습니다: 박테리아를 추가하는 것과 제거하는 것입니다. 정올이는 가장 오른쪽 풀밭인 N에서 서서 농약의 힘을 L로 설정합니다 (1 \leq L \leq N).

농약이 뿌려지면, 정올이의 가까운 풀밭에서 가장 큰 영향을 미치며, 먼 풀밭일수록 그 효과가 줄어듭니다. 정올이가 박테리아를 추가하는 농약을 선택하면, 풀밭 N에는 L 단위의 박테리아가 추가되고, 풀밭 N-1에는 L-1 단위가 추가되며, 풀밭 N-2에는 L-2 단위가 추가됩니다. 다시 말해, 풀밭 1 \ldots N-L은 농약의 힘이 충분하지 않아 영향을 받지 않습니다. 비슷하게, 박테리아를 제거하는 농약을 선택하면, 풀밭 N에서 L 단위의 박테리아가 제거되고, 풀밭 N-1에서 L-1 단위가 제거되며, 풀밭 N-2에서 L-2 단위가 제거됩니다. 마찬가지로, 풀밭 1 \ldots N-L은 영향을 받지 않습니다.

모든 풀밭이 건강한 박테리아 수준을 갖기 위해 정올이가 농약을 뿌려야 하는 최소 횟수를 구하십시오. 답은 최대 10^9 이내입니다.

주의: 이 문제에서 다루는 정수의 크기가 크기 때문에 64비트 정수 데이터 타입(예: C/C++의 "long long")을 사용할 필요가 있습니다.

#6215 upload 11 done 6 how_to_reg 6 call_split Subtask

박테리아 timer 1s memory 1024MB

#6215
Subtask

박테리아 1s 1024MB