TopCoder

Caido
主唱太拼命了

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

85.7% (6/7)

Tags

Description

今天,臺大程式解題社的其中 $N$ 位選手面向你站成了一個橫排,由左至右的編號為 $1\sim N$,身為這次活動負責人的你,被社長指派必須挑出一些人站出來進行機智問答,這些站出來的人只會往你的方向前進一步,並不會左右移動。不過,邪惡的社長為了增添你的麻煩,特別告訴你說你選出來參加問答的人選必須要滿足以下條件:

  • 一定要挑編號 $1$ 的人。
  • 一定要挑編號 $N$ 的人。
  • 對於任兩個在選出來的人當中相鄰的人,他們兩個人的編號差不可以小於 $2$。

你已經知道有幾種挑人的方法,因此調查了一遍每個人的問答能力值,分別為 $a_1, a_2, \ldots, a_N$,代表若第 $i$ 個人被挑選出來參加機智問答,他可以讓總能力值增加 $a_i$,注意到有些人的能力值是負的,代表你挑選他出來參加機智問答反而會讓總能力值變小(可能是因為他身體不舒服吧!)。

現在你的目標是要最大化挑選出來的人的總能力值,請問這個最大值會是多少呢?

Input Format

輸入首行有一個正整數 $N$,代表站在你面前的選手數。

次行 $N$ 個整數 $a_1, a_2, \ldots, a_N$,代表第 $i$ 個人的能力值為 $a_i$

  • $3 \leq N \leq 10^ 6$
  • $-10^ 9 \leq a_i\leq 10^ 9$

Output Format

輸出挑選出來的人的總能力值最大會是多少。

Sample Input 1

5
3 1 -4 1 5

Sample Output 1

8

Sample Input 2

7
2 1 5 9 5 1 8

Sample Output 2

20

Hints

Problem Source

程式解題社教學題。

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~10 無特別限制。 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2