Bytecomputer

A sequence of n integers x[1], x[2], ..., 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[1] ≤ x[2] ≤ ...≤ x[n]) with the minimum number of operations.

Input

The first line holds a single integer n (1 ≤ n ≤ 10^6), the number of elements in the (bytecomputer's) input sequence. The second line contains n integers x[1], x[2], ..., x[n] (x[i] 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.

Examples

Note

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