Yaroslav 有 n 个点位于 Ox 轴上。第一个点的坐标是x1,第二个点的坐标是x2,...,第n个点的坐标是—xn。现在Yaroslav想要执行m个查询,每个查询都是以下两种类型之一:
1. 将第 pj 个点从位置 xpj 移动到位置 xpj + dj。这样,可以保证执行此类查询后,所有点的坐标都是不同的。
2. 计算线段 [lj, rj] 上所有点对之间的距离总和 (lj ≤ rj)。换句话说,您应该计算以下总和:$$\sum_{l_j \leq x_p \leq x_q \leq r_j} (x_q - x_p)$$。
帮助雅罗斯拉夫。
输入
第一行包含整数 n — 点数 (1 ≤ n ≤ 105)。第二行包含不同的整数 x1, x2, ..., xn — 点的坐标 (|xi| ≤ 109)。
第三行包含整数 m — 查询数量 (1 ≤ m ≤ 105)。接下来的 m 行包含查询。第 j 行首先包含整数 tj (1 ≤ tj ≤ 2) — 查询类型。如果 tj = 1,则后面跟着两个整数 pj 和 dj (1 ≤ pj ≤ n,|dj| ≤ 1000)。如果 tj = 2,则后面跟着两个整数 lj 和 rj (- 109 ≤ lj ≤ rj ≤ 109)。
保证在任何时刻所有点都有不同的坐标。
输出
对于每个类型 2 查询,将答案打印在一行上。按顺序打印答案,其中查询紧随输入。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 %I64d 说明符的 cin、cout 流。
示例
输入 #1
8 36 50 28 -75 40 -60 -95 -48 20 2 -61 29 1 5 -53 1 1 429 1 5 130 2 -101 -71 2 -69 53 1 1 404 1 5 518 2 -101 53 2 50 872 1 1 -207 2 -99 -40 1 7 -389 1 6 -171 1 2 464 1 7 -707 1 1 -730 1 1 560 2 635 644 1 7 -677
输出 #1
176 20 406 1046 1638 156 0