Cathy’s favourite candy brand is releasing n new flavours of candy: one new flavour on each of the next n days. A pack of candy flavour i (the new flavour released on the i th day) will cost w_i dollars on the day that it is released, but in order to encourage customers to try the new flavours, each candy flavour increases in price by one dollar on each day after it has been released. Precisely, on day j ≥ i, a pack of the candy flavour released on day i costs</p>

w_i + (j − i)

dollars.

Cathy wants to buy exactly one pack of candy on each one of the next n days and wants to get the most candy for her money. Calculate the price of the cheapest pack of candy available on each of the next n days. There is an unlimited number of packs of each flavour of candy and each flavour is available on the day of its release and all subsequent days.

입력 형식

The input consists of two lines. The first line contains an integer n (1 ≤ n ≤ 200 000), which is the number of flavours. The second line contains n integers w₁, w₂, ..., w_n (1 ≤ w_i ≤ 100 000), where w_i is the initial price of the i th candy flavour in dollars.

출력 형식

Display n integers, the i th of which is the price of the cheapest pack of candy that Cathy can buy on day i.

예제 입력 1

4
3 6 7 4

예제 출력 1

3 4 5 4

예제 입력 2

4
22 22 28 24

예제 출력 2

22 22 23 24