P3558 [POI 2013] BAJ-Bytecomputer

给定一个由集合 $\{-1, 0, 1\}$ 中的 $n$ 个整数 $x_1, x_2, \cdots, x_n$ 组成的序列。字节计算机是一种允许对序列进行以下操作的设备：对于任何 $1 \leq i < n$，可以将 $x_{i+1}$ 改为 $x_{i+1} + x_i$。字节计算机可以存储的整数范围没有限制，即每个 $x_i$ 可以（原则上）具有任意小或大的值。 编程实现字节计算机，使其将输入序列转换为非递减序列（即 $x_1 \leq x_2 \leq \cdots \leq x_n$），并使操作次数最少。

标准输入的第一行包含一个整数 $n$ ($1 \leq n \leq 1000000$)，表示（字节计算机的）输入序列中的元素个数。 第二行包含 $n$ 个整数 $x_1, x_2, \cdots, x_n$ ($x_i \in \{-1, 0, 1\}$)，它们是（字节计算机的）输入序列的连续元素，元素之间用单个空格分隔。 在占总分 24% 的测试中，$n \leq 500$；在占总分 48% 的测试中，$n \leq 10000$。

标准输出的第一行应输出一个整数，即字节计算机必须执行的最小操作次数，以使其输入序列成为非递减序列；如果无法获得这样的序列，则输出单词 BRAK（波兰语，意为“无”）。

题面翻译由 ChatGPT-4o 提供。