Fafa 有一个包含 n 个正整数的数组 A,函数 f(A) 定义为 $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$。他想做 q 两种类型的查询:
- 1 l r x — 如果要将 x 添加到 [l, r] 范围内的一个元素,则求 f(A) 的最大可能值。您可以选择向哪个元素添加 x。
- 2 l r x — 将 [l, r] 范围内的所有元素增加 x 值。
请注意,类型 1 的查询不会影响数组元素。
输入
第一行包含一个整数 n (3 ≤ n ≤ 105) — 数组的长度。
第二行包含 n 个正整数 a1, a2, ..., an (0 < ai ≤ 109) — 数组元素。
第三行包含一个整数 q (1 ≤ q ≤ 105) — 查询数量。
接下来是 q 行,第 i 行描述第 i 个查询并包含四个整数 ti li ri xi $$( t _ { i } \in \{ 1, 2 \}, 1 < l _ { i } \leq r _ { i } < n, 0 < x _ { i } \leq 1 0 ^ { 9 } )$$。
保证至少有一个查询属于类型 1。
输出
对于类型 1 的每个查询,打印该查询的答案。
示例
输入 #1
5 1 1 1 1 1 5 1 2 4 1 2 2 3 1 2 4 4 2 2 3 4 1 1 3 3 2
输出 #1
2 8
输入 #2
5 1 2 3 4 5 4 1 2 4 2 2 2 4 1 2 3 4 1 1 2 4 2
输出 #2
6 10