Bacterial Level Adjustment

Farmer John has N patches of grass arranged in a row, numbered 1 through N. For each patch i, its bacterial level differs from the healthy level by an integer a_i (which may be negative or positive). If a_i < 0, then patch i is deficient and needs exactly |a_i| units of bacteria added. If a_i > 0, then patch i has an excess and needs exactly a_i units removed.

Farmer John can use a pesticide sprayer that comes in two types – one that adds bacteria and one that removes bacteria. When he uses the sprayer he stands at patch N (the right‐most patch) and sets its power level L (with 1 ≤ L ≤ N). The sprayer then affects exactly the L patches closest to him – specifically patches N-L+1, N-L+2, …, N – with a gradient effect. For an adding operation with power level L, patch N receives L units of bacteria added, patch N-1 receives L-1 units, patch N-2 receives L-2 units, and so on; patches 1 … N-L are unaffected. Similarly, a removal operation subtracts exactly the same amounts from the affected patches.

The goal is to achieve the healthy bacterial level on every patch (i.e. to make the net adjustment on patch i equal to -a_i). Find the minimum number of sprayer operations required. It is guaranteed that an answer exists and that it does not exceed 10⁹.

Note: Since the integers involved can be very large (up to about 10¹⁵ in absolute value) you may need to use 64‐bit integer types in some languages.

Explanation of the sample: For example, suppose N = 3 and a = [-1, -2, -3]. This means the patches require adjustments of [1, 2, 3] respectively. One way to fix this is to use one addition operation with power level L = 3 (which adds the sequence [1, 2, 3] to patches 1, 2, 3 respectively). In this case the answer is 1.

inputFormat

The first line contains a single integer N (1 ≤ N ≤ 2·10⁵).

The second line contains N space‐separated integers a₁, a₂, …, a_N (−10¹⁵ ≤ a_i ≤ 10¹⁵).

outputFormat

Output a single integer – the minimum number of sprayer operations needed to repair all the patches.

sample

3
-1 -2 -3

1