← 返回题目列表

AtCoder · abc388_d

G. 成人庆典

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

在某个星球上,有 N 外星人,全部都是未成年人。

的 树的 i- 第一个外星人目前有 A_i 石头,将成为成年人 i 几年后。

当某人在这个星球上成为成年人时,每个人 成人 至少拥有一颗石头的人正好给刚成年的外星人一颗石头作为祝贺礼物。

找出每个外星人之后将拥有多少石头 N 年。

假设未来不会再有新的外星人诞生。

约束

  • 1 \leq N \leq 5 \times 10^5
  • 0 \leq A_i \leq 5 \times 10^5
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

让 B_i 是该人拥有的宝石数量 i-第一个外星人之后 N 年。打印 B_1, B_2, \ldots, B_N 按此顺序,用空格分隔。


示例输入 1

4
5 0 9 3

示例输出 1

2 0 10 5

让 C_i 是 i-第一个外星人在给定时间有。

最初, (C_1, C_2, C_3, C_4) = (5, 0, 9, 3).

之后 1 年, (C_1, C_2, C_3, C_4) = (5, 0, 9, 3).

之后 2 年, (C_1, C_2, C_3, C_4) = (4, 1, 9, 3).

之后 3 年, (C_1, C_2, C_3, C_4) = (3, 0, 11, 3).

之后 4 年, (C_1, C_2, C_3, C_4) = (2, 0, 10, 5).


示例输入 2

5
4 6 7 2 5

示例输出 2

0 4 7 4 9

示例输入 3

10
2 9 1 2 0 4 6 7 1 5

示例输出 3

0 2 0 0 0 4 7 10 4 10