10004번 - Bytecomputer 다국어

문제

A sequence of n integers x₁,x₂,…,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 ≤ 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₁ ≤ x₂ ≤ … ≤ x_n) with the minimum number of operations.

입력

The first line of the standard input holds a single integer n (1 ≤ n ≤ 1,000,000), the number of elements in the (bytecomputer's) input sequence.

The second line contains n integers x₁,x₂,…,x_n (x_i ∈ {-1,0,1}) that are the successive elements of the (bytecomputer's) input sequence, separated by single spaces.

출력

The first and only line of the standard output should give 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.

제한

힌트

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