以下题面由 AI 翻译。

题目描述

给定一个包含 N（N ≤ 50000）个整数的序列 A，序列中每个整数的取值范围为 [-10000, 10000]。你需要对该序列执行 M（M ≤ 50000）次操作：

• 修改序列中第 i 个元素的值；
• 或对于给定的 x 和 y，输出区间 [x, y] 内的最大子段和，即 max{Ai + Ai+1 + ... + Aj | x ≤ i ≤ j ≤ y}。

输入格式

输入的第一行包含一个整数 N。
第二行包含 N 个整数，表示序列 A1 到 AN。
第三行包含一个整数 M。
接下来 M 行，每行描述一个操作，格式如下：

• 0 x y：将 Ax 修改为 y（|y| ≤ 10000）。
• 1 x y：输出区间 [x, y] 的最大子段和。

输出格式

对于每个操作类型为 1 的查询，输出一个整数表示结果。

样例数据

输入：

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

输出：

6
4
-3

数据范围

• 1 ≤ N ≤ 50000
• 1 ≤ M ≤ 50000
• 序列中每个元素及修改操作的 y 值均满足 |数值| ≤ 10000。