Background

子数组的最大和

Description

给定一个包含整数（可能为正数、负数或零）的数组，找出其中所有连续子数组的最大和。子数组是指数组中元素连续的一个子集，长度至少为 1。

Input

第一行包含一个整数 n（1 ≤ n ≤ 10^5），表示数组的长度 第二行包含 n 个整数，用空格分隔

Output

输出一个整数，表示所有连续子数组的最大和

Samples

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

6

Limitation

1s, 1024KiB for each test case.