给定一个长度为 $N$ 的整数数组 $A$（下标从 0 开始）。

考虑 $A$ 的一个长度为 $K$ 的子序列，元素的下标分别为 $0 \le i_0 < i_1 < i_2 < \ldots < i_{K-1} < N$，该子序列的价值被定为 $\displaystyle \sum_{0 \le t < K} (-1)^tA_{i_t}$.

现在，对于所有 $1 \le K \le N$，请你求出长度为 $K$ 的子序列的最大价值。

输入格式

第一行一个整数 $N$.

第二行 $N$ 个整数 $A_0,A_1,\ldots,A_{N-1}$.

输出格式

输出 $N$ 行，每行一个整数，第 $i$ 行表示长度为 $i$ 的子序列的最大价值。

输入输出中相邻两个整数用空格隔开。

样例输入

7
100 10 10 100 64 75 359

样例输出

359 90 449 126 485 -11 348

样例解释

• $K=1:359$
• $K=2:100-10=90$
• $K=3:100-10+359=449$
• $K=4:100-10+100-64=126$
• $K=5:100-10+100-64+359=485$
• $K=6:100-10+10-100+64-75=-11$
• $K=7:100-10+10-100+64-75+359=348$

子任务

对于所有数据，保证 $1 \le N \le 5 \times 10^5,-10^9 \le A_i \le 10^9$.

1. $N \le 5000$（15 分）
2. $0 \le A_i \le 2$（10 分）
3. $A_i$ 的种类数不超过 $5$（15 分）
4. $A_i \ge 1$（20 分）
5. $N \le 10^5$（20 分）
6. 没有特殊性质（20 分）

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$