AT_past202212_g 区間和

You are given an integer sequence of length $ N $ : $ A = (A_1, A_2, \ldots, A_N) $ . Print the maximum possible value of $ A_l + A_{l+1} + \cdots + A_r $ for a pair $ (l, r) $ such that $ 1 \leq l \leq r \leq N $ .

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Print the answer.

### Sample Explanation 1 For $ (l, r) = (2, 8) $ , we have $ A_2 + A_3 + \cdots + A_8 = 5 + (-3) + 3 + (-1) + 4 + (-1) + 5 = 12 $ , which is the maximum possible value. ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ -10^9 \leq A_i \leq 10^9 $ - All values in the input are integers.