Illuminated Lamps

Byteasar has installed n solar lamps in his garden. Each lamp illuminates a fixed angular range and all lamps face the same direction. The lamps are numbered from 1 to n and are supplied with electricity sequentially: lamp i gets electricity at time i. A lamp will start emitting light either when it receives electricity at time i or earlier if it is illuminated by at least k_i lamps.

Formally, let \(T[i]\) denote the time at which lamp \(i\) lights up. We have \(T[1]=1\). For \(i>1\), if the number of lamps that were turned on before lamp \(i\) is less than k_i (i.e. if \(k_i>i-1\)), then lamp \(i\) cannot be illuminated early and will light at time \(i\). Otherwise, let \(x\) be the k_i-th smallest value among \(T[1],T[2],\dots,T[i-1]\). Then lamp \(i\) lights at time \(T[i]=\min(i, x)\).

Note: When a lamp lights up (either because it received enough illumination or because it got powered), it immediately begins illuminating the subsequent lamps.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), the number of lamps.

The second line contains \(n\) space-separated integers \(k_1, k_2, \dots, k_n\). It is guaranteed that \(k_1 = 0\), and for \(i > 1\), \(1 \le k_i \le i\).

outputFormat

Output \(n\) space-separated integers, where the \(i\)-th integer is the time when lamp \(i\) lights up.

sample

5
0 1 1 2 3

1 1 1 1 1