题目描述

塔沃节快到了，Libra 和 Rahn 决定享用家乡的传统美食：烤兔头。

桌上有 $n$ 盘烤兔头排成一排，从左到右编号 $1\sim n$，第 $i$ 个盘子里有 $a_i$ 个烤兔头。经过商量，Libra 和 Rahn 决定各自从桌子的两端同时开始吃烤兔头，Libra 从左往右吃，Rahn 从右往左吃，两人吃兔头的速度相等，且都会先将当前的盘子内的烤兔头吃完后再吃下一盘，吃完的盘子会被后勤立刻撤走。由于 Libra 和 Rahn 还邀请了一些好友来品尝美食，所以当两人开始吃烤兔头前或吃完一个烤兔头后发现桌下只剩下 $\le k$ 盘烤兔头时会同时停止，剩余的烤兔头等好友们赴宴后再共同享用。

晚宴正在筹备的过程中，而 Libra 已经迫不及待的想要知道自己能吃多少烤兔头。然而筹备的过程总会发生意外，烤兔头的数量会因为一些原因（老鼠偷吃、厨师做好了新的烤兔头等）发生改变。Libra 会将这些信息告知你，并不时地询问你她能吃多少烤兔头。

输入

输入第一行一个整数 $n(1\le n\le 10^5)$，表示桌上的盘子数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，$a_i(1\le a_i\le 10^9)$ 表示从左到右第 $i$ 个盘子初始时的烤兔头数。

第三行一个整数 $q(1\le q\le 3\cdot 10^5)$，表示事件+询问的总次数。

接下来 $q$ 行，每行表示一个事件/询问：

• 1 x y：表示一个事件：第 $x$ 个盘子的烤兔头数变成了 $y$；
• 2 x：表示一个询问：Libra 想要知道当 $k=x$ 时自己能吃到的烤兔头数。$k$ 的含义见题目描述。

保证 $1\le x\le n, 1\le y\le 10^9$。

注意：因输入输出数据量较大，请尽量使用速度较快的 scanf/printf 进行输入输出，尽量避免使用速度较慢的 cin/cout。

输出

对于每个询问，输出一行一个整数表示答案。

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

2
4