Skyscrapers

You are not allowed to search for problem "skyscrapers" on Codeforces.

The outskirts of the capital are being actively built up in Berland. The company "Kernel Panic" manages the construction of a residential complex of skyscrapers in New Berlskva. All skyscrapers are built along a highway. It is known that the company has already bought $n$ plots along the highway and is preparing to build $n$ skyscrapers, one on each plot.

Architects must consider several requirements when planning the skyscrapers:

• Each plot has a limit on the maximum number of floors due to land properties.
• According to the city’s design code, it is unacceptable for a skyscraper to have both a taller skyscraper on its left and a taller skyscraper on its right.

Formally, label the plots from $1$ to $n$. Let $a_i$ be the number of floors of the skyscraper on plot $i$. Then:

• $1 \le a_i \le m_i$, for all $1 \le i \le n$, and
• There must not exist an index $i$, $1 < i < n$, such that $a_{i−1} > a_i < a_{i+1}$.

The company wants to maximize the total number of floors, i.e. $a_1 + a_2 + \ldots + a_n$.

Task

Find any valid configuration $a_1, a_2, \ldots , a_n$ that satisfies all constraints and maximizes the total number of floors.

Input data

The first line contains a single integer $n$.

The second line contains $n$ integers $m_1, m_2, \ldots , m_n$, where $m_i$ is the maximum allowed number of floors on plot $i$.

Output data

Print $n$ integers $a_1, a_2, \ldots , a_n$ — the number of floors for each skyscraper, such that all constraints are satisfied and the total number of floors is maximized.

If there are multiple valid answers, print any of them.

Constraints and clarifications

• $1 \le n \le 5 \cdot 10^5$
• $1 \le m_i \le 10^9$

Example 1

stdin

5
1 2 3 2 1

stdout

1 2 3 2 1

Explanation

Assigning maximum heights to all skyscrapers is valid.

Example 2

stdin

3
10 6 8

stdout

10 6 6

Explanation

Assigning maximum heights to all plots violates the constraint. The configuration $[10, 6, 6]$ is optimal. Another valid configuration is $[6, 6, 8]$, but it is not optimal since the total sum is smaller.