← 返回题目列表

Codeforces · 935/F

F. 发发与阵

中文机器翻译题面 查看原题

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