시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 512 MB222219100.000%

문제

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 wi 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

wi + (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 w1, w2, ..., wn (1 ≤ wi ≤ 100 000), where wi 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