Bytecomputer

Time limit3sMemory limit512 MB

Summary

Repeatedly add an entry to its right neighbor in a -1, 0, 1 sequence to make it non-decreasing with the fewest operations, or report BRAK if impossible.

Level: Medium7 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

You are given a sequence of $n$ integers $x_1, x_2, \dots, x_n$ , each of them from the set $\{-1, 0, 1\}$ . The bytecomputer is a device that allows one operation on the sequence: choose an index $i$ with $1 \le i < n$ and increase $x_{i+1}$ by $x_i$ . The range of integers the bytecomputer can store is unlimited, so in principle each $x_i$ can become arbitrarily small or arbitrarily large.

You want the sequence to be non-decreasing, that is, $x_1 \le x_2 \le \dots \le x_n$ . Find the minimum number of operations needed.

Input

The first line contains one integer $n$ , the length of the sequence ( $1 \le n \le 1\,000\,000$ ).

The second line contains the $n$ elements of the sequence $x_1, x_2, \dots, x_n$ in order, separated by single spaces ( $x_i \in \{-1, 0, 1\}$ ).

Output

Print on one line the minimum number of operations that make the sequence non-decreasing. If no sequence of operations achieves that, print BRAK instead. BRAK is Polish for none.

Hint

Three operations turn the sequence $-1, 1, 0, -1, 0, 1$ into $-1, -1, -1, -1, 0, 1$ .

Examples2

Example 1
Input
```
6
-1 1 0 -1 0 1
```
Expected output
```
3
```
Example 2
Input
```
2
0 -1
```
Expected output
```
BRAK
```