Description

给定N个元素的整数列（可能为负数）a1,a2,a3,,,an ,求形如 ai,ai+1,ai+2,,,aj (i,j在[1,n]之间，i<=j)的子段，使其和最大。

Format

Input

输入数据有多组。每组输入两行，第一行是数字的个数N，第二行N个数字，中间用空格隔开.

Output

输出最大子段和

Samples

6
-2 11 -4 13 -5 -2

20

Hint