Description

上次数学考试考了一道这样的题目：一个有n个整数的数字序列，其间有正负整数，

现在的任务是求出两段不相交的连续子序列，使这两段中的数字和最大。

Format

Input

第一行，一个数n，表示整数的个数。

第二行n个数，描述这个序列。 n<=1000000

Output

仅一行，表示最大的数字和

Samples

10
1 2 -3 2 1 4 -3 2 1 2 

12

Hint

//（取子序列 2， 1， 4 和 2， 1， 2，得到最大的和）