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。