【题目背景】
朋友？哼，有些人终成不了朋友；而朋友，真的只是时期段的吗？
【题目描述】
因比赛题目特设此题：
对于给定一个长度为 \(n\) 的序列 \(A\)（\(a_1,a_2...a_n\)，首尾相连），求选择若干个不相邻数且必须选择 \(a_i\) 的情况下，所选数的和最大为多少 \(sum_i\)。（\(i∈[1,n]\)）
【输入格式】
第一行一个数 \(n\)。
第二行 \(n\) 个数，为 \(a_i\)。
【输出格式】
共 \(n\) 行，每行一个数，为 \(sum_i\)。
【样例输入1】

3
-1 0 1

【样例输出1】

-1
0
1

【样例输入2】

6
-1 1 -1 -1 1 -1

【样例输出2】

0
2
0
0
2
0

【样例输入3】

7
1 2 3 4 5 6 7

【样例输出3】

11
14
15
13
15
12
15

【提示/说明】
时空限制：\(2s\)，\(256MiB\)。

测试点序号	\(n\)	\(\lvert a_{i}\rvert\)	特殊性质
\(1\sim 2\)	\(\leq 7\)	\(\leq 10\)	\(N\)
\(3\sim 4\)	\(\leq 3*10^3\)	\(\leq 10^5\)	\(N\)
\(5\sim 7\)	\(\leq 2*10^5\)	\(\leq 10^8\)	\(Y\)
\(8\sim 10\)	\(\leq 2*10^6\)	\(\leq 10^8\)	\(N\)

特殊性质：
\(N\)：没有任何特殊性质。
\(Y\)：对于 \(i∈[1,n]\)，\(a_i\geq 0\)。

对于 \(100\%\) 的数据，\(3\leq n\leq 2*10^6\)，\(-10^8\leq a_i\leq 10^8\)。
推荐时间复杂度：\(O(n)\)。（这道题 \(O(n\log n)\) 好像能过诶！）