Description

Given a sequence $a$ of length $n$, choose a non-empty contiguous subarray whose sum is maximized.

Input Format

The first line contains an integer $n$, the length of the sequence. The second line contains $n$ integers; the $i$-th is $a_i$.

Output Format

Output one line with a single integer, the answer.

7
2 -4 3 -1 2 -4 3

4

Hint

• Explanation for Sample 1: Choose the subarray $[3, 5]$, which is $\{3, -1, 2\}$; its sum is $4$.
• Constraints:
  • For 40% of the testdata, it is guaranteed that $n \le 2 \times 10^3$.
  • For 100% of the testdata, it is guaranteed that $1 \le n \le 2 \times 10^5$ and $-10^4 \le a_i \le 10^4$.

Translated by ChatGPT 5