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 candygrams, all organized in a line. Each candygram has an *explosiveness*, denoted by . 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 -th candygram is an *EMP candygram*, it will not be able to disable a candygram in the line if there are strictly less than 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 .

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

#### Constraints

For all subtasks:

##### Subtask 1 [20%]

##### Subtask 2 [80%]

#### Input Specification

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

lines follow, each with an integer. The -th line is equal to , the *explosiveness* of the -th candygram.

#### Output Specification

You are to print out lines, the -th of which includes an integer, the *annoyance* of the -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 candygrams between the first and second candygram; and candygram between the first and third. Both of these are less than . As for the fourth and fifth candygram, the largest *explosiveness* is .

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

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

The fourth candygram cannot hit any other candygram.

The fifth candygram can hit the first candygram. Its *annoyance* is .

## Comments