AdditionalFile5014.zip

#5014. 「POI2013 R3」字节计算机 Bytecomputer

标签: 传统 | 时间限制: 1000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XX Olimpiada Informatyczna — III etap Bajtokomputer

给定一个长度为 $n$ 的整数序列 $x_1, x_2, \ldots, x_n$，每个元素的值属于 $\{-1, 0, 1\}$。字节计算机是一种特殊设备，仅支持一种操作：对于任意 $1 \leq i < n$，将 $x_{i+1}$ 的值增加 $x_i$。字节计算机可存储任意大的整数，序列元素的值无上限。

请编程控制字节计算机，使用最少的操作次数将给定序列转换为非降序序列，即满足 $x_1 \leq x_2 \leq \ldots \leq x_n$。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 1000000)$，表示序列长度。

第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$ $(x_i \in \{-1, 0, 1\})$，表示序列的元素，彼此间用单个空格分隔。

输出格式

输出一行，包含一个整数，表示字节计算机将序列转换为非降序序列所需的最少操作次数；若无法实现，输出 BRAK。

样例 1

输入

6
-1 1 0 -1 0 1

输出

3

通过三次操作，字节计算机可将序列转换为 $-1, -1, -1, -1, 0, 1$。

样例 2

输入

6
0 0 -1 -1 1 1

输出

BRAK

附加样例

1. $n=6$，小型样例，答案为 $4$。
2. $n=500$，序列所有元素均为 $1$。
3. $n=10000$，$x_1 = x_2 = \ldots = x_{9000} = -1$，$x_{9001} = \ldots = x_{9900} = 1$，$x_{9901} = \ldots = x_{10000} = 0$。
4. $n=1000000$，$x_1 = x_2 = \ldots = x_{999997} = -1$，$x_{999998} = 1$，$x_{999999} = 1$，$x_{1000000} = -1$。

数据范围与提示

对于 $24\%$ 的测试数据，$n \leq 500$。
对于 $72\%$ 的测试数据，$n \leq 10000$。