Background

给定一个整数数组，找到具有最大和的连续子数组（至少包含一个元素）。请使用暴力枚举方法解决，即枚举所有可能的子数组并计算它们的和。

Input

输入格式

• 第一行包含一个整数 n (1 ≤ n ≤ 1000)，表示数组的长度
• 第二行包含 n 个整数，表示数组元素，每个整数的绝对值不超过 10000

Output

• 输出一个整数，表示最大子数组和

Samples

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

6