Bytecomputer Sequence Transformation

You are given a sequence of \(n\) integers \(x_1,x_2,\cdots,x_n\) where each \(x_i\) is initially from the set \(\{-1,0,1\}\). A device called the bytecomputer can perform the following operation on the sequence: for any index \(1\le i\le n-1\), it increments \(x_{i+1}\) by the current value of \(x_i\) (i.e. \(x_{i+1} \gets x_{i+1} + x_i\)). There is no bound on the magnitude of the numbers involved.

Your task is to program the bytecomputer so that it transforms the input sequence into a non-decreasing sequence, i.e. a sequence satisfying

[ x_1 \le x_2 \le \cdots \le x_n, ]

using the minimum number of operations.

Note: It is guaranteed that the input sequence is such that the transformation is possible.

inputFormat

The first line contains a single integer \(n\) \((1\le n \le 10^5)\), the number of elements in the sequence.

The second line contains \(n\) space‐separated integers \(x_1,x_2,\cdots,x_n\), each of which is initially either \(-1\), \(0\), or \(1\).

outputFormat

Output a single integer representing the minimum number of operations required to transform the sequence into a non-decreasing sequence.

sample

3
1 0 -1

3