1226 - 数列

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / Writer ei1941 / x 7 / 統計 /


TLE
1sec
MLE
64MB
得点
100

問題

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

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

入力

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

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

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

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

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

出力

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

制約

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

  • 1 ≦ N ≦ 105
  • 0 ≦ Q ≦ 105
  • -104valuei ≦ 104
  • -104aj ≦ 104
  • 1 ≦ liri ≦ 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である。