该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

给定一个数列，从中找到3个无交集的连续子数列使他们的和最大

Input

第一行一个数n，表示数列长度。

接下来有n行，每行一个数，第i行为第i个数。

Output

仅有一个数，表示最大和。

Samples

10
-1
2
3
-4
0
1
-6
-1
1
-2

7

Limitation

对于30%的数据，n<=200。

对于60%的数据，n<=2000。

对于100%的数据，n<=1000000。