说明

给定一个数字序列，求它的一个子序列，使其和最大。

输入格式

输入的第一行为一个数n；(n<= 500)

第二行开始有n个数，每个数( < 1000 )之间用空格隔开

输出格式

输出最大子序列和

样例

6
2 -5 1 -7 8 9 

17