TopCoder

abcabcabc

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

39.3% (11/28)

Description

天府城有一排土地由左到右編號 $1\sim N$，每塊土地有他蓋一棟建築帶來的價值。你想要在這裏投資一些土地並建起一些房屋，然而由於連續的房屋失火時容易蔓延，你希望投資的所有房屋不會恰形成一段完整的連續區間（也就是說，不存在 $l, r$ 使得對於所有房屋 $x$，$x$ 被你投資若且唯若 $l \le x \le r$），並且你不能全部不投資房屋。你的投資總收益是你在所有蓋房屋的土地上收益總和。請你回答在滿足條件下的最大收益。

Input Format

本題包含多筆測資，輸入第一行是一個整數 $T$，代表測資筆數。

每筆測資輸入兩行，第一行是一個整數 $N$，代表土地數量。
第二行有 $N$ 個空白分隔的整數 $a_i (1\le i\le N)$，代表投資第 $i$ 塊土地價值。

輸入保證 $T\le 10^ 5$，$3\le N\le 3\times 10^ 5$，$-1000\le a_i\le 1000$，且單筆輸入所有 $N$ 總和不超過 $3\times 10^ 5$。

Output Format

對於每筆測資輸出一行一個整數，代表最大投資收益。

Sample Input 1

2
5
-5 6 2 -4 0
5
-3 2 1 7 -4

Sample Output 1

8
9

Sample Input 2

1
3
-1 5 3

Sample Output 2

Hints

Problem Source

NPSC

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~9	無額外限制	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

794 . 投資建案