题目描述

商店在过去的 $N$ 天中每天都会以价格 $p_1,p_2,\dots,p_N$ 买卖某种物品。

你可以进行若干次交易，每次交易由两个下标 $i<j$ 决定，表示在第 $i$ 天买入、在第 $j$ 天卖出，这次交易的利润为：

在任意时刻，你至多只能持有一件该物品。因此，不同交易之间不能“交叉”。更形式化地说，若你进行的交易依次为

则必须满足：

对于固定的 $K$，求“至多进行 $K$ 次交易时的最大利润”并不难；现在你需要对每个 $K$（$1\le K\le N$）都求出对应的最大利润。

输入格式

第一行输入一个整数 $N$（$1\le N\le 500000$），表示天数。
第二行输入 $N$ 个整数 $p_1,p_2,\dots,p_N$（$1\le p_i\le 10^9$），表示每天的价格。

输出格式

输出 $N$ 个整数，其中第 $K$ 个整数表示：当最多允许进行 $K$ 次交易时，可以获得的最大利润。

数据范围与子任务

样例输入

10
90 10 30 20 40 35 30 50 40 70

样例输出

60 70 80 90 90 90 90 90 90 90

样例解释

这 $10$ 天的价格依次为：

用 $X^+$ 表示“以价格 $X$ 买入”，用 $-X$ 表示“以价格 $X$ 卖出”。

下面给出若干种最优方案：