您的尋寶團隊剛剛發現了一個巨大的考古遺址，裡面充滿了貴金屬和珍貴的古物。該遺址由一條線上的 $n$ 個挖掘點組成。

初步計畫顯示，這 $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