Hossa (Bull Market)

Consider a sequence $a_1, a_2, \ldots, a_n$ of $n$ distinct natural numbers. We call this sequence a hossa (a bull market) if for every three positions $i < j < k$ the following holds: whenever $a_i < a_j$, we have $a_k > a_i$.

Intuitively, if between two days $i$ and $j$ the price rose from $a_i$ to $a_j$ (that is, $a_i < a_j$), then on no later day does the price ever fall back to $a_i$ or below.

For example, the 14 hossas made of the elements $1, 2, 3, 4$ are:

$(1,2,3,4),\ (2,1,3,4),\ (1,3,2,4),\ (3,1,2,4),\ (3,2,1,4),\ (1,2,4,3),\ (2,1,4,3),\ (1,4,2,3),\ (1,4,3,2),\ (4,1,2,3),\ (4,2,1,3),\ (4,1,3,2),\ (4,3,1,2),\ (4,3,2,1)$

By contrast, $(3,2,4,1)$ is not a hossa, because the price rose from $3$ to $4$ and later fell to $1$.

Every hossa can be written as $L\,m\,P$, where $m$ is the largest value, $L$ is the elements to the left of $m$, and $P$ is the elements to the right of $m$. For instance, in the hossa $(1,2,4,3)$ we have $m = 4$, $L = (1,2)$, and $P = (3)$. Both $L$ and $P$ are themselves hossas made of fewer elements.

For two different hossas $H_1 = L_1\,m\,P_1$ and $H_2 = L_2\,m\,P_2$ built from the same numbers (one is a permutation of the other), we define $H_1 < H_2$ as follows:

1. If $P_1$ has fewer elements than $P_2$, then $H_1 < H_2$.
2. If they have the same number of elements, compare whether the hossa $P_1$ is smaller than the hossa $P_2$ (that is, $P_1 < P_2$).
3. If $P_1$ and $P_2$ are exactly the same sequence, compare whether $L_1 < L_2$.

Sorting the hossas made of $1, 2, 3, 4$ by this order gives the list shown above. Some comparisons:

• $(1,2,3,4) < (2,1,3,4)$: by rule 3 it reduces to $(1,2,3) < (2,1,3)$, which by rule 3 reduces to $(1,2) < (2,1)$, which holds by rule 1.
• $(1,4,2,3) < (1,4,3,2)$: by rule 2 it reduces to $(2,3) < (3,2)$.

Given a hossa $H$, output its immediate successor $X$: the unique hossa $X$ such that

• $H < X$, and
• $X < H'$ for every other hossa $H'$ with $H < H'$.

You may assume that such an $X$ always exists for the given input. For example, the immediate successor of $(1,2,3,4)$ is $(2,1,3,4)$, the successor of $(2,1,3,4)$ is $(1,3,2,4)$, and the next one is $(3,1,2,4)$.

The first line contains an integer $n$ ($2 \le n \le 10^6$). The second line contains $n$ distinct natural numbers, separated by single spaces, each at most $10^6$; these are the elements of some hossa $H$.

Print the $n$ natural numbers of the immediate successor of the hossa $H$ on one line, separated by single spaces.