时间限制：1秒　　内存限制：256M

---

【问题描述】

　　对于一个含 \(n\) 个整数的序列: \(A={a_1,a_2,...,a_n}\)，我们定义函数 \(d(A)\) 的意义如下：
　　　
　　现在输入一个序列 \(A\)，请你计算 \(d(A)\)。
　　PS：通俗地说，\(d(A)\) 的含义就是“序列 \(A\) 的两个不相交子序列的最大和”

【输入格式】

　　第 1 行为整数 \(n\)，表示序列 \(A\) 的元素个数。
　　第 2 行为 \(n\) 个整数：\(a_1,a_2,...,a_n\)。

【输出格式】

　　一个整数，表示 \(d(A)\) 的值。

【输入输出样例1】

　Input

10
1 -1 2 2 3 -3 4 -4 5 -5

　Output

13

【数据限制】

　　\(2≤n≤500000\)
　　\(|a_i|≤10000\)

【来源】

　Mr.he