D. Три последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Вы должны построить две последовательности целых чисел $$$b$$$ и $$$c$$$ длины $$$n$$$, которые удовлетворяют условиям:

  • для всех $$$i$$$ ($$$1\leq i\leq n$$$) $$$b_i+c_i=a_i$$$;
  • $$$b$$$ неубывающая, что означает, что для всех $$$1<i\leq n$$$, выполнено $$$b_i\geq b_{i-1}$$$;
  • $$$c$$$ невозрастающая, что означает, что для всех $$$1<i\leq n$$$, выполнено $$$c_i\leq c_{i-1}$$$.

Вы хотите минимизировать $$$\max(b_i,c_i)$$$. Другими словами, вы хотите минимизировать максимум чисел в последовательностях $$$b$$$ и $$$c$$$.

Также будет сделано $$$q$$$ изменений, $$$i$$$-е изменение описывается тройкой чисел $$$l,r,x$$$. Вы должны добавить $$$x$$$ к $$$a_l,a_{l+1}, \ldots, a_r$$$.

Вы должны найти минимальное значение $$$\max(b_i,c_i)$$$ для изначальной последовательности и для последовательности после каждого изменения.

Входные данные

В первой строке находится единственное целое число $$$n$$$ ($$$1\leq n\leq 10^5$$$).

Во второй строке находится $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq i\leq n$$$, $$$-10^9\leq a_i\leq 10^9$$$).

В третьей строке находится единственное целое число $$$q$$$ ($$$1\leq q\leq 10^5$$$).

Каждая из следующих $$$q$$$ строк содержит три целых числа $$$l,r,x$$$ ($$$1\leq l\leq r\leq n,-10^9\leq x\leq 10^9$$$), описывающих очередное изменение.

Выходные данные

Выведите $$$q+1$$$ строку.

В $$$i$$$-й ($$$1 \leq i \leq q+1$$$) строке выведите ответ на задачу для последовательности после $$$i-1$$$ изменения.

Примеры
Входные данные
4
2 -1 7 3
2
2 4 -3
3 4 2
Выходные данные
5
5
6
Входные данные
6
-9 -10 -9 -6 -5 4
3
2 6 -9
1 2 -10
4 6 -3
Выходные данные
3
3
3
1
Входные данные
1
0
2
1 1 -1
1 1 -1
Выходные данные
0
0
-1
Примечание

В первом тесте:

  • Изначальная последовательность $$$a = (2, -1, 7, 3)$$$. Пара последовательностей $$$b=(-3,-3,5,5),c=(5,2,2,-2)$$$ является возможным выбором.
  • После первого изменения $$$a = (2, -4, 4, 0)$$$. Пара последовательностей $$$b=(-3,-3,5,5),c=(5,-1,-1,-5)$$$ является возможным выбором.
  • После второго изменения $$$a = (2, -4, 6, 2)$$$. Пара последовательностей $$$b=(-4,-4,6,6),c=(6,0,0,-4)$$$ является возможным выбором.