Колонна из $n$ самокатов едет по узкой односторонней дороге в пункт Б. Самокаты пронумерованы от $1$ до $n$. Для каждого самоката $i$ известно, что текущее расстояние от него до пункта Б равно $a_i$ метров. При этом $a_1 \lt a_2 \lt \ldots \lt a_n$, в частности, самокат $1$ находится ближе всего к пункту Б, а самокат $n$ — дальше всего.

Самокат с номером $i$ движется в сторону пункта Б со скоростью $i$ метров в секунду (то есть чем ближе самокат в колонне к пункту Б, тем медленнее он едет). Так как дорога узкая, самокаты не могут обгонять друг друга. Более того, соседние самокаты в колонне должны соблюдать дистанцию хотя бы в $1$ метр. Поэтому когда более быстрый самокат догоняет более медленный, более быстрому приходится дальше ехать со скоростью более медленного, причём на расстоянии в $1$ метр от него.

Определите, на каком расстоянии до пункта Б будет каждый самокат ровно через одну секунду.

Input

В первой строке задано одно целое число $n$ ($1 \le n \le 100$) — число самокатов в колонне.

В $i$-й из следующих $n$ строк задано одно целое число $a_i$ ($1 \le a_i \le 1000$; $a_1 \lt a_2 \lt \ldots \lt a_n$) — текущее расстояние от самоката $i$ до пункта Б в метрах.

Output

Выведите $n$ целых чисел — расстояния от самокатов $1, 2, \ldots, n$ до пункта Б в метрах через одну секунду.

Note

В первом тесте самокаты пока не мешают друг другу ехать, поэтому каждый самокат $i$ продвигается на $i$ метров в сторону пункта Б.

Во втором тесте самокаты уже выстроились в колонне на расстоянии $1$ метр друг от друга и вынуждены ехать со скоростью самого медленного самоката с номером $1$.

Samples

4
20
30
50
100

19
28
47
96

5
1
2
3
4
5

0
1
2
3
4

8
5
9
10
15
17
18
19
22

4
7
8
11
12
13
14
15