CF2242F.Summer Vacation

While reading the statement of this problem, we recommend forgetting that summer consists of $92$ days and that a day consists of $1440$ minutes. This is Berland, and things are different here.

Monocarp is a student at a provincial university in Berland. The summer holidays have just begun, and they will last for the next $n$ days. Monocarp has long dreamed of going to the capital of Berland, so he will choose one day $i$ among these days, arrive in the capital on that day, and spend the rest of the holidays there.

The capital of Berland is not a very cheap city, and Monocarp has $0$ Berland dollars with him. Naturally, this is not enough to visit interesting places and buy souvenirs. Therefore, on some days in the capital, Monocarp will work as a freelancer. He does not want to work in his hometown, since he has already spent the whole academic year doing university assignments.

Formally, on the $i$-th day of the holidays, Monocarp will have $a_i$ free minutes, which he will spend either working or resting and buying souvenirs. If Monocarp has at least $a_i$ dollars at the beginning of the $i$-th day, then on that day he will spend them on rest and souvenirs at a rate of $1$ dollar per minute; that is, during this day, he will spend $a_i$ dollars. Otherwise, he will spend this time working, earning $1$ dollar per minute; that is, during this day, he will earn $a_i$ dollars. Note that Monocarp always makes his decision for the entire day; it is impossible for him to both spend and earn money during the same day.

Your task is to determine, for each number of days $k$ from $1$ to $n$, how many dollars Monocarp will have left after the last day of the holidays if he lives in the capital for exactly $k$ last days (i. e. if he arrives on the day $(n-k+1)$).

阅读本题题面时，我们建议暂时忘记“夏季共有 $92$ 天”以及“一天有 $1440$ 分钟”这些常识。这是贝尔兰（Berland），这里的情况有所不同。

Monocarp 是贝尔兰某省立大学的一名学生。暑假刚刚开始，将持续接下来的 $n$ 天。Monocarp 一直梦想着前往贝尔兰首都，因此他将从这 $n$ 天中选择某一天 $i$，于该日抵达首都，并在首都度过剩余全部假期。

贝尔兰首都并非一座廉价城市，而 Monocarp 身上仅有 $0$ 贝尔兰元。显然，这点钱不足以游览名胜、购买纪念品。因此，在首都逗留期间的某些天里，Monocarp 将以自由职业者身份工作。他不愿在家乡工作，因为整个学年他已忙于完成大学课业。

形式化地，设假期第 $i$ 天 Monocarp 拥有 $a_i$ 分钟空闲时间，他将用这些时间要么工作，要么休息并购买纪念品。若第 $i$ 天开始时 Monocarp 至少拥有 $a_i$ 元，则当天他将把全部钱用于休息与购物，花费速率为每分钟 $1$ 元；即当天他将恰好花费 $a_i$ 元。否则，他将利用全部空闲时间工作，收入速率为每分钟 $1$ 元；即当天他将恰好赚取 $a_i$ 元。注意：Monocarp 每天的决策是整体性的；同一天内他不可能既花钱又赚钱。

你的任务是：对每个 $k = 1, 2, \dots, n$，计算当 Monocarp 恰好在假期最后 $k$ 天（即于第 $(n-k+1)$ 天）抵达首都并居住至假期结束时，他在假期最后一天结束后所剩余的钱数（单位：贝尔兰元）。

The first line contains one integer $n$ ($1 \le n \le 10^{5}$).

The second line contains $n$ integers $a_{i}$ ($1 \le a_{i} \le n$).

第一行包含一个整数 $n$（$1 \le n \le 10^{5}$）。

第二行包含 $n$ 个整数 $a_{i}$（$1 \le a_{i} \le n$）。

Print $n$ integers, where the $k$-th integer must be equal to the number of dollars Monocarp will have left if he lives in the capital for exactly $k$ last days (i. e. if he arrives on the day $(n-k+1)$).

输出 $n$ 个整数，其中第 $k$ 个整数必须等于：若 Monocarp 恰好在首都居住最后 $k$ 天（即他在第 $(n-k+1)$ 天抵达），则他最终剩余的美元数量。

null