# B6. 學妹表示太難不想去建中上課（TooHard）

## Problem Statement

> 建電面試 - 學術專用題 pG：
> > 你會比較想教難一點的東西還是入門一點的東西，為什麼？
>
> > 那如果今天你的對幹或是其他學術跟你說他覺得這個別人會聽不懂，你會怎麼辦？

$Repkironca$ 剛寫完物理，他發現自己不管怎麼跑，永遠都脫離不了簡諧運動的魔掌。因此，所以他決定過來出學術上機考的題目，以噁心學弟妹為樂。

然而，剛剛的物理已經把他腦細胞燒光，導致她壓根想不到題敘。他想出的題目，用白話文來說是這樣的：
:::info
給定 $N$ 個數字 $x$ 排成一列，今天我要在裡面取出一些數字保留，並盡可能使我保留的數字總和最大。然而，在取數字時有一項限制：**我必須一次拿走 3 個相鄰的數字，且保留中間那個。至於左右兩個數字，會被無情地捨棄**。當場上數字不到 3 個時，就不能再行拿取。

舉例來說，如果 $N = 6$，這是一個可能的情況：``2 4 5 9 7 6``。你可以先拿走 ``4 5 9``，並且保留 ``5``，此時場上還剩下 ``2 7 6``。接著再拿走 ``2 7 6``，並且保留 ``7``。

你保留的數字總和是 ``5 + 7 = 12``，顯然，這並不是最佳解。
:::
正當 $Repkironca$ 思考著這道題該怎麼寫時（對，他自己還沒想到正解，超級糟糕），一道熟悉的聲音響起：

＂*你出得太難了吧，輸光，大家都不會寫*＂

原來，當初面試中的那個 **其他學術**，aka 嗯嗯出現了。他告訴 $Repkironca$ 一個殘忍的事實：


這下好了，大家會不會寫，$Repkironca$ 根本不在意。但如果沒有學妹要打比賽，這會危及到建北電資的核心價值。此時，嗯嗯又冷不及防地補了一句：

＂*任何一個有常識跟良知的人，都知道在出題前，自己必須先解出答案吧*＂

哇咧，不愧是嗯嗯，她精準打到了 $Repkironca$ 的痛點。無奈之下，$Repkironca$ 把題目簡單化了一些：

:::info
給定 $N$ 個數字 $x$ 排成一列，今天我要在裡面選擇一些數字，並盡可能使我選擇的數字總和最大。然而，在選數字時有一項限制：一旦我選擇第 $K$ 個數字，則第 $K-1$ 與第 $K+1$ 個數字就不能再被選擇了。當然，如果你選擇的數字恰好在邊界，就只有一側的數字會受到影響。

你不見得要將數字選完，如果你想要，甚至可以一個數字都不選，總和就會是 0

一個數字被選擇後仍然待在原地，不會被移出陣列。舉一個 N = 6 的例子 ``2 4 5 9 7 6``，你可以選擇 ``2 5 7``，這種選法的總和是 ``14``。又或者，你可以選擇 ``4 9 6``，這種選法的總和是 ``19``，顯然後者比較理想。
:::

＂*這樣可以了嗎？*＂$Repkironca$ 問道
＂*看起來不錯，至少這題我會寫*＂ 嗯嗯滿意地回答
＂*噢好耶，小雞芒果拉瑪冰*＂

嗯對，事情至此結束。$Repkironca$ 回去寫他的物理，他剛剛把問題丟給姜姜，現在知道解答了。而嗯嗯跑去吃全家霜淇淋，不知道是這星期的第幾支，反正目前的白葡萄口味她吃得很開心。

不過有個小問題：$Repkironca$ 跟嗯嗯兩人，都沒有把解答說出來。為了不讓這題變成費馬大定理，螢幕前的你能夠幫忙寫出這題的 AC 解，拯救整個資訊界嗎？

## Input Format

一開始吃進一個正整數 $N$，代表總共有多少數字
下一行有 $N$ 個數字 $x$ 排成一列，中間以空格分開，意義請見題敘

- $1 \leq N \leq 10^6$
- $-10^9 \leq x \leq 10^9$

## Output Format

請輸出你所選擇的數字總和，盡可能讓其最大

## Sample

### Input

6
2 4 5 9 7 6

### Output

19

### Input

6
7 -3 0 14 -18 -5

### Output

21

## Scoring

每個 Subtask 獨立計算，取聯集，滿分 100 分
若未特別提及，測資範圍均與題敘吻合

- Subtask.1（8%）保證 $\forall x_i×x_{i+1} \leq 0 \land 2 \leq N \leq 1000$
<!--1 to 6-->
- Subtask.2（7%）保證 $1 \leq N \leq 10$
<!--7 to 12-->
- Subtask.3（26%）保證 $0 \leq x_i \leq 10^9 \land 2 \leq N \leq 1000$
<!--13 to 18-->
- Subtask.4（59%）無額外限制
<!--19 to 30-->
## Hint



###### tags: `2023建北電資學術上機考`