e-olymp
Competitions

2013 Петрозаводск, День 6, Август 29, Задачи А - С

Bytecomputer

A sequence of n integers x1, x2, ..., xn from the set {-1, 0, 1} is given. The bytecomputer is a device that allows the following operation on the sequence: incrementing xi+1 by xi for any 1i < n. There is no limit on the range of integers the bytecomputer can store, i.e., each xi 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 x1x2 ≤ ...≤ xn) with the minimum number of operations.

Input

The first line holds a single integer n (1n106), the number of elements in the (bytecomputer's) input sequence. The second line contains n integers x1, x2, ..., xn (xi from {-1, 0, 1}) that are the successive elements of the (bytecomputer's) input sequence.

Output

Print one integer - the minimum number of operations the bytecomputer has to perform to make its input sequence non-decreasing, of the single word BRAK (Polish for none) if obtaining such a sequence is impossible.

Explanation

With three operations, the bytecomputer can obtain the sequence -1, -1, -1, -1, 0, 1.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
6
-1 1 0 -1 0 1
Output example #1
3
Source 2013 Petrozavodsk Training Camp, Day 6, August 29, Problem B