柏林首都有n栋多层建筑,这些的房子都建在一排。
让我们从左到右列举所有的房子,从第一栋开始。如果一栋房子的楼层数严格大于位于其右侧的所有房子,那么它就是豪华的。
建筑师ZZ想装修这些房子,让房子看起来更豪华,他提了以下问题:“第i栋房子应该加多少层才能让它变得豪华?”(对于从1到n的所有i,包括n)。你需要帮助他完成这项任务。
请注意,所有这些问题都是相互独立的——房屋i问题的答案不影响其他答案(即房屋的楼层实际上没有增加)。
输入的第一行包含单个数字n(1≤n≤105) ——柏林首都的房屋数量。
第二行包含n个空格分隔的正整数hi(1≤hi≤109),其中hi等于第i栋房子的楼层数。
打印n个整数a1,a2,…,an,其中数字ai是需要添加到房屋编号i上以使其豪华的楼层数。如果房子已经很豪华,不需要添加任何东西,那么ai应该等于零。
所有的房子都从左到右编号,从一开始。
示例
输入
5
1 2 3 1 2
输出
3 2 0 2 0
输入
4
3 2 1 4
输出
2 3 4 0
5 1 2 3 1 2
3 2 0 2 0
4 3 2 1 4
2 3 4 0
5
1 2 3 1 2
3 2 0 2 0