← 返回题目列表

Codeforces · 581/B

B. 豪华住宅

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

贝尔兰的首都有n栋多层建筑。建造都城的建筑师非常有创意,所以所有的房屋都建造成一排。

让我们从左到右枚举所有房屋,从一栋开始。如果一栋房屋的层数严格大于所有层数较多的房屋,则该房屋被认为是豪华的。换句话说,如果一栋房子的层数严格大于其右侧所有房子的层数,那么该房子就是豪华的。在此任务中,假设房屋的楼层高度相同。

新建筑师对n个问题感兴趣,其中第i个问题是关于以下问题的:“第i栋房子应该加多少层才能变得豪华?” (对于从 1 到 n 的所有 i,包括 1 和 n)。你需要帮助他完成这项任务。

请注意,所有这些问题都是相互独立的 - 房屋 i 问题的答案不会影响其他答案(即,房屋的楼层实际上并未添加)。

输入

输入的第一行包含一个数字 n (1 ≤ n ≤ 105) — Berland 首都的房屋数量。

第二行包含 n 个空格分隔的正整数 hi (1 ≤ hi ≤ 109),其中 hi 等于第 i 栋房子的层数。

输出

打印n个整数a1, a2, ..., an,其中数字ai是需要添加到门牌号i以使其变得豪华的楼层数。如果房子已经很豪华,不需要添加任何东西,那么ai应该等于0。

所有房屋从左到右编号,从一开始。

示例

输入 #1

5
1 2 3 1 2

输出 #1

3 2 0 2 0

输入 #2

4
3 2 1 4

输出 #2

2 3 4 0