1226 - 数列

問題

数列Aの要素に以下の操作を加えた後、連続して並ぶ任意個の整数の和の最大値を求める。

• 数列Aのl番目からr番目にvalueを足す。

入力

N
a1 a2 ... an
Q
l1 r1 value1
.
.
.
lQ rQ valueQ

1 行目に数列 A の個数を表すNが与えられる。

2 行目に数列 Aの要素a_j が空白区切りで与えられる。

3 行目に数列が変化する回数Qが与えられる。

4 行目からQ+3行目にかけて数列Aが変化する範囲l_i, r_iと元の値に足す数値 value_iが与えられる。

出力

連続して並ぶ任意個の整数の和の最大値を出力する。

制約

全ての入出力ケースについて以下を満たす。

• 1 ≦ N ≦ 10⁵
• 0 ≦ Q ≦ 10⁵
• -10⁴ ≦ value_i ≦ 10⁴
• -10⁴ ≦ a_j ≦ 10⁴
• 1 ≦ l_i ≦ r_i ≦　N

i , jは以下の条件を満たす

• 0 ≦ i ≦　Q
• 0 ≦ j ≦　N

---

入出力例

入力例1

5
2 3 4 5 6
2
1 3 1
3 5 -6

出力例1

7

解説

数列Aの要素2 3 4 5 6がある。
1回目の操作の範囲は1から3であり、それらの範囲に1が足される。
なので数列Aの1から3の範囲の要素2 3 4は+1され3 4 5になる。
2回目の操作の範囲は3から5であり、それらの範囲に-6が足される。
なので数列Aの3から5の範囲の要素5 5 6は-6され-1 -1 0になる。
操作を全て終了した後の数列Aの要素は 3 4 -1 -1 0になる。
この数列の連続して並ぶ任意個の整数の最大値は7となる。

入力例2

6
10 24 23 1 12 21
3
1 5 10
3 6 -9
1 6 -5

出力例2

75

入力例3

5
-10 -11 -12 -13 -14
3
1 5 5
2 3 -2
3 5 -3

出力例3

0

このときの出力は0である。