题目描述

我们称一个整数数组 $d_1, d_2, \ldots, d_m$ 为好的，如果其长度为 $0$，或者对于任意 $1 \le i \le m$，$\sum\limits_{j=1}^{i} d_j$ 和 $\sum\limits_{j=i}^{m} d_j$ 都非负。其中 $\sum\limits_{j=l}^{r} d_j$ 表示 $d_l + d_{l+1} + \ldots + d_r$。

我们定义数组的 美丽值 为其最长 好的 子序列$^1$的长度。

给定一个长度为 $n$ 的数组 $a$，其元素仅由 $-1$ 和 $1$ 组成。

你需要处理 $q$ 个查询，查询分为两种类型：

• 将元素 $a_p$ 替换为 $-a_p$，其中 $p$ 为查询参数；
• 查询由元素 $[a_{l}, a_{l+1}, \ldots, a_r]$ 组成的数组的 美丽值，其中 $(l, r)$ 为查询参数。

输入格式

第一行包含两个整数 $n$, $q$ $(1 \le n, q \le 5 \cdot 10^5)$ —— 数组 $a$ 的长度和查询的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(a_i \in \{-1, 1\})$ —— 数组 $a$ 的元素。

接下来的 $q$ 行描述查询。第一个数字 $type_i$ $(1 \le type_i \le 2)$ 表示查询类型。类型为 $1$ 的查询格式为 $\texttt{1 p}$ $(1 \le p \le n)$，类型为 $2$ 的查询格式为 $\texttt{2 l r}$ $(1 \le l \le r \le n)$。

输出格式

对于每个类型为 $2$ 的查询，输出一行一个整数 —— 对应数组的美丽值。

输入输出样例 #1

输入 #1

5 4
1 1 1 -1 1
2 1 5
1 3
2 1 4
2 2 5

输出 #1

5
2
3

输入输出样例 #2

输入 #2

4 4
1 1 1 -1
2 1 2
2 2 4
2 3 3
2 3 4

输出 #2

2
2
1
1

说明/提示

$^1$ 数组 $c$ 称为数组 $b$ 的子序列，如果可以通过从 $b$ 中删除若干元素（可能为零）得到 $c$。空数组是任何数组的子序列。

评分标准

• （$2$ 分）：对于所有 $1 \le i \le n$，$a_i = (-1)^{i+1}$，且没有类型 $1$ 的查询；
• （$7$ 分）：$n \le 16$，且没有类型 $1$ 的查询；
• （$21$ 分）：$n, q \le 100$；
• （$20$ 分）：$n, q \le 3000$；
• （$27$ 分）：$n, q \leq 2 \cdot 10^5$，且没有类型 $1$ 的查询；
• （$14$ 分）：$n, q \leq 2 \cdot 10^5$；
• （$9$ 分）：无额外限制。