AT_past202212_g 区間和

長さ $ N $ の整数列 $ A = (A_1, A_2, \ldots, A_N) $ が与えられます。 $ 1 \leq l \leq r \leq N $ を満たす整数の組 $ (l, r) $ を任意に選ぶときの、 $ A_l + A_{l+1} + \cdots + A_r $ の値としてあり得る最大値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 $ (l, r) = (2, 8) $ のとき、 $ A_2 + A_3 + \cdots + A_8 = 5 + (-3) + 3 + (-1) + 4 + (-1) + 5 = 12 $ であり、これが最大です。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ -10^9 \leq A_i \leq 10^9 $ - 入力はすべて整数