题目背景

翻译自 CSES-1643 题。

题目描述

给定 $n$ 个整数（可能为负），你的任务是找出和最大的连续子序列（至少包含一个元素）。

输入格式

第一行输入一个整数 $n$，第二行输入 $n$ 个整数。

输出格式

输出最大子序列和。

样例

8
-1 3 -2 5 3 -5 2 2

9

说明/提示

$1 \le n \le 2\cdot 10^5$，$-10^9 \le x_i \le 10^9$。