给定一个长度为 $N$ 的数列 $A_1, A_2, \ldots, A_N$。请编写程序处理以下查询：

• 1 i v：将 $A_i$ 修改为 $v$（$1 \le i \le N$，$1 \le v \le 10^9$）。
• 2 l r：输出所有满足 $l \le i < j \le r$ 的 $A_i + A_j$ 中的最大值（$1 \le l < r \le N$）。

数列的索引从 $1$ 开始。

输入格式

第一行包含一个整数 $N$，表示数列的长度（$2 \le N \le 100{,}000$）。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$1 \le A_i \le 10^9$）。

第三行包含一个整数 $M$，表示查询的个数（$2 \le M \le 100{,}000$）。

接下来 $M$ 行，每行描述一个查询。

输出格式

对于每个类型 $2$ 的查询，按照顺序在一行中输出答案。

样例

输入

5
5 4 3 2 1
6
2 2 4
2 1 4
1 5 5
2 3 5
1 4 9
2 3 5

输出

7
9
8
14