Candy Sales

Cathy's favourite candy brand is releasing n new flavours, one new flavour on each of the next n days. A pack of flavour $i$, the flavour released on day $i$, costs $w_i$ dollars on its release day. To get customers to try the new flavours, the price of a flavour goes up by one dollar on each day after its release. On day $j \ge i$, a pack of the flavour released on day $i$ costs

$w_i + (j - i)$

dollars.

Cathy buys exactly one pack of candy on each of the next n days and wants to get the most candy for her money. Compute the price of the cheapest pack of candy available on each of the next n days. Every flavour has an unlimited number of packs and is on sale on its release day and on all later days.

The input consists of two lines. The first line contains an integer $n$ ($1 \le n \le 200\,000$), the number of flavours. The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 100\,000$), where $w_i$ is the release-day price of flavour $i$ in dollars.

Print n integers on one line, separated by single spaces. The i-th integer is the price of the cheapest pack of candy that Cathy can buy on day i.