背景

夏日炎炎，最好的消暑活动莫过于游泳了。这天，小方得到了一个长方形的橡胶泳池，他打算邀请小块和小鸟来家里一起玩水。

描述

关于小方、小块、小鸟缝缝补补一个二手泳池度过夏天的故事，终于到了最后一集啦！

一个暑假下来，这个二手泳池越来越经不起折腾了，橡胶越来越破，从最初的只靠两块隔板就可以撑住泳池到现在需要$N$块隔板来撑住泳池，这个二手泳池估计快要退役了。

小方习惯了每天中午的时候开始把水管搭在最左侧的地方，拧开龙头往泳池里放水。接下来，这些被隔板隔开的隔间就会从左到右依次被注水。过了这么久，小方已经知道，龙头的水的流速是均匀的。而每个隔间底面积相同，因此水面每秒上升1个单位。

小方突然想到，隔板高度不一，而每个隔间都需要等水位高过左边隔板才会有水流进来，那这些隔间首次有水的时刻，会不会隐藏了下次考试选择题的选项呢？

记开始注水的时刻为$0$，需要你编写程序帮小方打印出每个隔间首次有水的时刻。

输入输出格式

输入

两行，第一行为一个正整数 $N$，表示一共有多少块隔板。 ($1 ≤ N ≤ 100,000$)

第二行为$N$个正整数$H_1, H_2, H_3, ..., H_N$，表示每块隔板的高度。 ($1 ≤ H_i < 10^9$)

输出

一行，为$N$个以空格分割的整数，表示每个隔间首次有水的时刻。

样例

5
3 1 4 1 5

4 5 13 14 26

样例1说明