As a harmless Halloween prank, Patrick has decided to fire candygrams at students that were projected to receive them. To make the prank even more amusing, he also decided to offer the steak he was planning on eating for lunch to the spirits wandering around the school. In return, he asked them to make his candygrams explosive! However, the student council caught wind of this mischievous plan and decided to smuggle an EMP candygram into Patrick's stash, which can remove the explosiveness from some of his candygrams.

Patrick has ~N~ candygrams, all organized in a line. Each candygram has an explosiveness, denoted by ~R_i~. While normal candygrams simply explode, an EMP candygram behaves a little differently. EMP candygrams are great at affecting candies in a wide range but don't affect candygrams near it. More specifically, if the ~i~-th candygram is an EMP candygram, it will not be able to disable a candygram in the line if there are strictly less than ~R_i~ candygrams in between them. However, it will be able to disable all other candygrams in the line.

Patrick soon realized what the student council was up to, and while he doesn't know which candygram he placed in the line was an EMP candygram, he still wanted to be prepared. Thus, Patrick has asked you, his best friend and trusty computer scientist, to help him calculate the annoyance of each candygram. The annoyance of a candygram is the largest explosiveness of all candygrams that it would be able to disable if it were an EMP candygram. If it cannot hit any other candygrams, then its annoyance is ~-1~.

For this question, Python users are recommended to use PyPy in order to pass the time limit.

Constraints

For all subtasks:

~0 \le R_i < N~

Subtask 1 [20%]

~0 < N \le 1000~

Subtask 2 [80%]

~0 < N \le 10^6~

Input Specification

The first line contains an integer ~N~, denoting the number of candygrams in Patrick's line.

~N~ lines follow, each with an integer. The ~(i+1)~-th line is equal to ~R_i~, the explosiveness of the ~i~-th candygram.

Output Specification

You are to print out ~N~ lines, the ~i~-th of which includes an integer, the annoyance of the ~i~-th candygram.

Sample Input

5
2
3
1
3
3

Sample Output

3
-1
3
-1
2

Sample Explanation

The first candygram cannot hit the second or third, as there are ~0~ candygrams between the first and second candygram; and ~1~ candygram between the first and third. Both of these are less than ~2~. As for the fourth and fifth candygram, the largest explosiveness is ~3~.

The second candygram cannot hit any other candygrams, as there are less than ~3~ candygrams between the second candygram and all other candygrams. Thus, its annoyance is ~-1~.

The third candygram can hit the first and fifth candygram. The maximum explosiveness is ~3~.

The fourth candygram cannot hit any other candygram.

The fifth candygram can hit the first candygram. Its annoyance is ~2~.