AT_pakencamp_2018_day3_d なぎさちゃんの別荘

### 题目简述 有一个 $n$ 点 $(n-1)$ 边的无向图。点的标号从 $1$ 到 $n$，第 $i$ 条边连接点 $i$ 和点 $i+1$，边权为 $c_i$。 请你求出：对于每个满足 $1\le i\le n$ 的整数 $i$，在图中找到的以点 $i$ 为一端的一条链中，边权和的最大值。

第一行输入一个整数 $n$。 第二行到第 $n$ 行，第 $(i+1)$ 行输入整数 $c_i$。

输出 $n$ 行，每行一个整数，表示第 $i$ 个答案。**建议在输出末尾添加换行。**

#### 样例 #1 解释 参见下图。  #### 数据规模与约定 **本题设有子任务。** **子任务 #1（15 pts）：** $n\le 1000$，$c_i\ge 0$。 **子任务 #2（30 pts）：** $c_i\ge 0$。 **子任务 #3（55 pts）：** 无特殊限制。 对于全部测试数据，$2\le n\le 100000$，$-10^9\le c_i\le 10^9$。