Distributing Coins

You are given the scores of n players in a game. Your task is to assign each player a certain number of coins according to the following rules:

• Each player must receive at least one coin.
• A player with a higher score must receive more coins than any of his adjacent players with lower scores.

The goal is to minimize the total number of coins distributed while following the above constraints.

Note: The players are arranged in the order of input and the comparison is only done with adjacent players.

Mathematical Formulation:

If we denote the score of the i^th player by \(s_i\) and the coins assigned by \(c_i\), then the constraints are:

\[ \begin{aligned} &\forall i,\; c_i \geq 1, \\ &\text{if } s_i > s_{i-1} \text{ then } c_i > c_{i-1}, \\ &\text{if } s_i > s_{i+1} \text{ then } c_i > c_{i+1}. \end{aligned} \]

You need to implement a solution that reads the input from stdin and writes the result to stdout as a sequence of numbers separated by a single space.

inputFormat

The first line of input contains a single integer n (the number of players). The second line contains n space-separated positive integers representing the scores of the players.

For example:

3
1 2 2

outputFormat

Output a single line containing n space-separated integers where the i^th integer is the number of coins assigned to the i^th player.

For example:

1 2 1

## sample

3
1 2 2

1 2 1