小乌龟不小心掉进了香城大峡谷的底处！小X经过听到他在大峡谷下的求救，于是报了警。在等待香城救援队的来临，小X决定把一些水倒进去给口渴的小乌龟。

小X在洞上看，发现香城大峡谷深$10^{18}$，而阔度为$N$。他用了一个大小为$N$的序列$A$来表达崎岖不平的大峡谷底。序列$A$表达的是峡谷底左至右岩石的高度，$A_1$是最左的岩石，$A_N$是最右的岩石。

为了让小乌龟轻松喝到倒下去的水，倒下去的水必须盖过小乌龟的全身。留意水会向低的地方流。每阔度为1，高度为1的水为1个单元的水量。

可是小X不知道小乌龟的确实位置。于是他找你帮忙计算，对于所有位置$i$，找出若小乌龟在第$i$块岩石上，他至少需要多少水才能让小乌龟轻松喝到。

输入格式

输入的第一行包含一个整数$N$表示香城大峡谷的阔度。
第二行包含$N$个正整数$A_1,A_2,...,A_N$，表示峡谷底左至右岩石的高度。

输出格式

输出1行$N$个整数，第$i$个整数表示若小乌龟在第$i$块岩石上，需要多少水才能让小乌龟轻松喝到。

数据范围

对于所有的测试数据，保证：
$1 \le N \le 10^6$
$1 \le A_i \le 10^9$

注意不寻常的时间限制!!!

特殊性质A：保证$A_i \le A_i+1$
特殊性质B：保证$A_1 \ge A_2 \ge ... \ge A_K \le ... \le A_N-1 \le A_N$ ($1 \lt K \lt N$)
特殊性质C：保证$A_i \le 30$

Credits:
turtle from: https://hadrian.cc/
stones and soil from: minecraft