A11615. 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:

- $1lrx$ — 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$ .
- $2lrx$ — increase all the elements in the range $[l,r]$ by value $x$ .

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

The first line contains one integer $n$ $(3<=n<=10^{5})$ — the length of the array.

The second line contains $n$ positive integers $a_{1},a_{2},...,a_{n}$ $(0<a_{i}<=10^{9})$ — the array elements.

The third line contains an integer $q$ $(1<=q<=10^{5})$ — 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$ .

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