你的寻宝团队刚刚发现了一个巨大的考古遗址，里面充满了贵金属和珍贵的文物。该遗址由排成一行的 $n$ 个挖掘点组成。

初步计划显示，每个挖掘点都有一个与之相关的净利润。第 $i$ 个点的相关利润为 $p_i$。具体来说，这意味着你的团队在第 $i$ 个点每挖掘一米，就能获得 $p_i$ 美元的收益。注意，$p_i$ 也可能是负数，这意味着挖掘机械的运行成本超过了在第 $i$ 个点挖掘的实际收益。

自然，你希望在利润最高的点尽可能多地挖掘。然而，为了防止发生滑坡，不允许坡度过陡。更准确地说，对于任意两个相邻的挖掘点，其挖掘深度之差不能超过 1 米。特别地，第 1 个点和第 $n$ 个点最多只能挖掘 1 米深。

在这些条件下，你能获得的最大净利润是多少？

例如，第一个样例输入中一个最优的挖掘方案如下图所示。该方案的净利润为 8。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 250\,000$)。

第二行包含 $n$ 个整数 $p_i$ ($-10^6 \le p_i \le 10^6$)，以空格分隔。

输出格式

输出一个整数，即你能获得的最大利润。

样例

输入格式 1

5
1 3 -4 2 1

输出格式 1

8

输入格式 2

4
1 1 -2 3

输出格式 2

5

输入格式 3

5
-1 -3 0 -5 -4

输出格式 3

0