CF935F.Fafa and Array

Fafa has an array A of n positive integers, the function f(A) is defined as . He wants to do q queries of two types:

• 1 l r x — find the maximum possible value of f(A), if x is to be added to one element in the range [l,  r]. You can choose to which element to add x.
• 2 l r x — increase all the elements in the range [l,  r] by value x.

Note that queries of type 1 don't affect the array elements.

Fafa 有一个包含 $n$ 个正整数的数组 $A$，函数 $f(A)$ 定义为 。他需要执行 $q$ 次查询，查询分为两类：

• 1 l r x —— 在区间 $[l,\,r]$ 中的某个元素上加上 $x$（可任选该区间内哪一个元素），求此时 $f(A)$ 的最大可能值。
• 2 l r x —— 将区间 $[l,\,r]$ 内所有元素均增加 $x$。

注意：类型 1 的查询不会修改数组中的元素。

The first line contains one integer n (3 ≤ n ≤ 105) — the length of the array.

The second line contains n positive integers _a_1, _a_2, ..., a__n (0 < a__i ≤ 109) — the array elements.

The third line contains an integer q (1 ≤ q ≤ 105) — the number of queries.

Then q lines follow, line i describes the i-th query and contains four integers t__i l__i r__i x__i .

It is guaranteed that at least one of the queries is of type 1.

第一行包含一个整数 $n$（$3 \leq n \leq 10^5$）—— 数组的长度。

第二行包含 $n$ 个正整数 $a_1,\,a_2,\,...,\,a_n$（$0 < a_i \leq 10^9$）—— 数组元素。

第三行包含一个整数 $q$（$1 \leq q \leq 10^5$）—— 查询的数量。

接下来 $q$ 行，第 $i$ 行描述第 $i$ 个查询，包含四个整数 $t_i\ l_i\ r_i\ x_i$ 。

保证至少有一个查询的类型为 1。

For each query of type 1, print the answer to the query.

对于每个类型为 1 的查询，输出该查询的答案。