[POI2013] BAJ-Bytecomputer

题意翻译

给定一个长度为 $n$ 的只包含 $-1,0,1$ 的数列 $a$,每次操作可以使 $a_i\gets a_i+a_{i-1}$,求最少操作次数使得序列单调不降。如果不可能通过该操作使得序列单调不降,请输出 `BRAK`。 数据范围:$1\le n\le 10^6$。

题目描述

A sequence of ![](http://main.edu.pl/images/OI20/baj-en-tex.1.png) integers ![](http://main.edu.pl/images/OI20/baj-en-tex.2.png) from the set ![](http://main.edu.pl/images/OI20/baj-en-tex.3.png) is given. The bytecomputer is a device that allows the following operation on the sequence: incrementing ![](http://main.edu.pl/images/OI20/baj-en-tex.4.png) by ![](http://main.edu.pl/images/OI20/baj-en-tex.5.png) for any ![](http://main.edu.pl/images/OI20/baj-en-tex.6.png). There is no limit on the range of integers the bytecomputer can store, i.e., each ![](http://main.edu.pl/images/OI20/baj-en-tex.7.png) 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 ![](http://main.edu.pl/images/OI20/baj-en-tex.8.png)) with the minimum number of operations.

输入输出格式

输入格式


The first line of the standard input holds a single integer ![](http://main.edu.pl/images/OI20/baj-en-tex.9.png) (![](http://main.edu.pl/images/OI20/baj-en-tex.10.png)), the number of elements in the (bytecomputer's) input sequence. The second line contains ![](http://main.edu.pl/images/OI20/baj-en-tex.11.png) integers ![](http://main.edu.pl/images/OI20/baj-en-tex.12.png) (![](http://main.edu.pl/images/OI20/baj-en-tex.13.png)) that are the successive elements of the (bytecomputer's) input sequence, separated by single spaces. In tests worth 24% of the total points it holds that ![](http://main.edu.pl/images/OI20/baj-en-tex.14.png), and in tests worth 48% of the total points it holds that ![](http://main.edu.pl/images/OI20/baj-en-tex.15.png).

输出格式


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.

输入输出样例

输入样例 #1

6
-1 1 0 -1 0 1

输出样例 #1

3