问题 H: 豪华住宅

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:536 通过:196

题目描述

柏林首都有n栋多层建筑,这些的房子都建在一排。

让我们从左到右列举所有的房子,从一栋开始。如果一栋房子的楼层数严格大于位于其右侧的所有房子,那么它就是豪华的。

   建筑师ZZ想装修这些房子,让房子看起来更豪华,他提了以下问题:i栋房子应该加多少层才能让它变得豪华?(对于从1n的所有i,包括n)。你需要帮助他完成这项任务。

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

输入格式

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

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



输出格式

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

所有的房子都从左到右编号,从一开始。 

  

示例 

输入 


1 2 3 1 2 

输出 

3 2 0 2 0 

输入 


3 2 1 4 

输出 

2 3 4 0 

Input
5
1 2 3 1 2
Output
3 2 0 2 0 
Input
4
3 2 1 4
Output
2 3 4 0 

输入样例 复制

5 
1 2 3 1 2

输出样例 复制

3 2 0 2 0