题目描述

Aoi 在享受静静流逝的宁静时光。

Aoi 有一个序列 $\{a_i\}$，她希望这个序列的最大前缀和尽可能的大。她可以做至多 $k$ 次操作，每次操作选择一个元素，翻转它的符号（即，把它替换成它的相反数）。她记进行至多 $k$ 次操作后，可以获得的最大前缀和为 $f(k)$（前缀可以是空，和为 $0$）。

求一个单独的 $f(k)$ 对她来说太简单了，所以她希望求出 $f(0),f(1),\ldots,f(n)$ 的所有值，这样她就可以拷打 Akari 和 Yuzu。由于 Akari 和 Yuzu 还有 1 秒就会赶到，所以她想迅速知道答案。

因为 Aoi 接下来一整个学期都想拷打 Akari 和 Yuzu，所以她把接下来每天获得的序列都一起告诉了你。你需要对每个序列分别求出答案。

输入格式

第一个一个正整数 $n$，代表序列的长度。

第二行共 $n$ 个数，第 $i$ 个数为 $a_i$，即序列的第 $i$ 项。

输出格式

一行共 $n+1$ 个整数，代表当前询问下 $f(0),f(1),\ldots,f(n)$ 的值。

5
-3 4 -2 -3 1

1 7 9 13 13 13

数据范围

• 对于 $30\%$ 的数据，$1 \le n \le 20$；
• 对于 $60\%$ 的数据，$1 \le n \le 1000$；
• 对于 $100\%$ 的数据，$1 \le n \le 5 \cdot 10^4$，$-10^9 \le a_i \le 10^9$。