SP1716 GSS3 - Can you answer these queries III

给定一个长度为 $N$ 的整数序列 $A$。有 $M$ 个操作，操作共有两种类型： 1. 修改序列中的第 $i$ 个元素。 2. 对于给定的区间 $[x, y]$，求 $\max\{A_i + A_{i+1} + \dots + A_j \mid x \le i \le j \le y\}$。

第一行包含一个整数 $N$。 第二行包含 $N$ 个整数，表示序列 $A_1, A_2, \dots, A_N$。 第三行包含一个整数 $M$。 接下来的 $M$ 行，每行包含一个操作，格式如下： - `0 x y`：将 $A_x$ 修改为 $y$（$|y| \le 10000$）。 - `1 x y`：输出 $\max\{A_i + A_{i+1} + \dots + A_j \mid x \le i \le j \le y\}$。

对于每个类型为 $1$ 的询问，根据题目要求输出一个整数。

对于所有数据：$N, M \le 50000, -10000 \le A_i \le 10000$。