F. Фафа и массив
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Фафы есть массив A из n положительных чисел, определим функцию f(A) как . Он хочет обработать q запросов двух типов:

  • 1 l r x — найти максимальное возможное значение f(A), если к одному из элементов отрезка [l,  r] предварительно добавить x. Вы можете выбирать, к какому элементу добавить 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 .

Гарантируется, что есть хотя бы один запрос типа 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
Выходные данные
2
8
Входные данные
5
1 2 3 4 5
4
1 2 4 2
2 2 4 1
2 3 4 1
1 2 4 2
Выходные данные
6
10