[POI2013]BAJ-Bytecomputer

题意翻译

给一个只包含-1,0,1的数列,每次操作可以让a[i]+=a[i-1],求最少操作次数使得序列单调不降 数据范围为N<=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