贝尔兰的首都有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