题目描述

给定一个由集合 $\{-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$ 可以（原则上）具有任意小或大的值。

题目给定 $q$ 个操作。每个操作先给定一个 $op$。 $op$ 为 $0$： 再输入两个数 $x, y$ ，将 $x_{i} = y$， $y \in \{-1, 0, 1\}$

$op$ 为 $1$： 编程实现字节计算机，使其将输入序列转换为非递减序列（即 $x_1 \leq x_2 \leq \cdots \leq x_n$），并使操作次数最少，输出这个操作次数。

输入格式

标准输入的第一行包含两个整数 $n$，$q$ ($1 \leq n, q \leq 100000$) 表示（字节计算机的）输入序列中的元素个数。

第二行包含 $n$ 个整数 $x_1, x_2, \cdots, x_n$ ($x_i \in \{-1, 0, 1\}$)，它们是（字节计算机的）输入序列的连续元素，元素之间用单个空格分隔。

接下来 $q$ 行，每行是 $op$，当 $op$ 为 $0$ 时，每行有三个数，表示 $op, x, y$

输出格式

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

输入输出样例 #1

输入 #1

6 6
-1 1 0 -1 0 1
1
0 3 1
1
0 1 0
0 2 -1
1

输出 #1

3
3
BRAK