Candy Sales

Interview

Time limit6sMemory limit512 MB

Summary

For each day j, print the minimum over all i at most j of w_i + (j - i).

Level: Medium5 of 10
Topics: Array, Prefix sum, Implementation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples2

Example 1
Input
```
4
3 6 7 4
```
Expected output
```
3 4 5 4
```
Example 2
Input
```
4
22 22 28 24
```
Expected output
```
22 22 23 24
```