一名运动员正在参加一项结合了跳房子和三级跳远的新运动。在这项比赛中，地面上排成一行放置了 $n$ 个方格，它们之间的距离相等。第一阶段是助跑，运动员冲向第一个方格，并在那里开始他们的第一次跳跃。随后，他们可以跳到任意数量的其他方格上，并最终必须落在最后一个方格中。

典型的跳房子场地，这项新运动的灵感来源。

裁判为跳入每个方格设定了预定的分数，运动员的得分将是他们跳入的所有方格的分数之和，包括第一个和最后一个方格。

由于这项运动的特性，一旦运动员开始跳跃，他们就不能再加速，且连续跳跃的距离绝不能增加。当然，也不可能改变跳跃方向。

给定裁判为每个方格分配的分数，求运动员在这项比赛中可能获得的最高得分。

输入格式

输入包含： 一行包含一个整数 $n$ ($2 \le n \le 3000$)，表示方格的数量。 一行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($-10^9 \le p_i \le 10^9$)，表示裁判为跳入每个方格所奖励的分数。

输出格式

输出运动员可能获得的最高得分。

样例

样例输入 1

4
1 -1 1 1

样例输出 1

3

样例输入 2

4
1 1 -1 1

样例输出 2

2

样例输入 3

3
-1 1 -1

样例输出 3

-1

样例输入 4

3
-1 -1 -1

样例输出 4

-2