Bytecomputer#6480
A sequence of integers x_1, x_2, \ldots, x_n from the set \{-1, 0, 1\} is given. The bytecomputer is a device that allows the following operation on the sequence: incrementing x_{i+1} by x_i for any 1 \leq i < n. There is no limit on the range of integers the bytecomputer can store, i.e., each x_i can (in principle) have arbitrarily small or large value.
Program the bytecomputer so that it transforms the input sequence into a non-decreasing sequence (i.e., such that x_1 \leq x_2 \leq \ldots \leq x_n) with the minimum number of operations.
The first line holds a single integer (1 \leq n \leq 10^6), the number of elements in the bytecomputer's input sequence. The second line contains integers x_1, x_2, \ldots, x_n (x_i from \{-1, 0, 1\}) that are the successive elements of the bytecomputer's input sequence.
Print one integer — the minimum number of operations the bytecomputer has to perform to make its input sequence non-decreasing, or the single word BRAK (Polish for none) if obtaining such a sequence is impossible.
Example 1
With three operations, the bytecomputer can obtain the sequence -1, -1, -1, -1, 0, 1.