给定一个包含 $n$ 个整数 $x_{1}, x_{2}, \dots, x_{n}$ 的序列，其中每个元素均属于集合 $\{-1, 0, 1\}$。Bytecomputer 是一种允许对序列执行以下操作的设备：对于任意 $1 \le i < n$，将 $x_{i+1}$ 增加 $x_{i}$。Bytecomputer 对存储的整数范围没有限制，即原则上每个 $x_{i}$ 都可以取任意大小的值。

请编写程序，通过最少次数的操作，将输入序列转换为非递减序列（即满足 $x_{1} \le x_{2} \le \dots \le x_{n}$）。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示序列中元素的个数。

第二行包含 $n$ 个整数 $x_{1}, x_{2}, \dots, x_{n}$ ($x_{i} \in \{-1, 0, 1\}$)，表示输入序列的各个元素，以空格分隔。

输出格式

输出一行，包含一个整数，表示将序列变为非递减序列所需的最少操作次数。如果无法得到这样的序列，则输出 BRAK。

样例

输入 1

6
-1 1 0 -1 0 1

输出 1

3

说明 1

通过三次操作，Bytecomputer 可以得到序列 -1, -1, -1, -1, 0, 1。