[R39D]购买股票 - 代码源竞赛平台

时空限制

1S/512M

题目描述

apiadu 正在开发一套自动股票交易系统。给定一个长度为 $n$ 的数组 $P$，其中 $P_i$ 表示某支股票在第 $i$ 天的价格。

该系统的交易策略如下： 假设 apiadu 在第 $j$ 天以价格 $P_j$ 买入了一股股票，他会一直持有，直到遇到第一个价格严格高于 $P_j$ 的日子 $i$（即 $i > j$ 且 $P_i > P_j$），并在第 $i$ 天将其卖出。

如果直到第 $n$ 天结束都没有遇到价格高于 $P_j$ 的日子，那么这笔交易就不会发生（或者说无法在第 $n$ 天及之前卖出）。

现在，apiadu 想知道每一天的“结算收益”。对于每一天 $i$，请你计算：假设所有满足“在第 $i$ 天卖出”这一条件的交易都在当天结算，那么这些交易的总利润是多少？

格式

输入格式

第一行包含一个整数 $n$，表示天数。

第二行包含 $n$ 个整数 $P_1, P_2, \dots, P_n$，表示每天的股票价格。

输出格式

输出一行，包含 $n$ 个整数，第 $k$ 个整数表示第 $k$ 天的总利润。数与数之间用空格隔开。

样例

样例输入 #1

5
5 3 2 4 6

样例输出 #1

0 0 0 3 3

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \le$	$P_i \le$
$1$	$40$	$1000$	$10^9$
$2$	$60$	$5 \times 10^5$

对于 $100\%$ 的数据， $1 \le n \le 5 \times 10^5$， $1 \le P_i \le 10^9$。