Morty and the Password

Interview

Time limit2sMemory limit1024 MB

Summary

Given a permutation where each cup can be touched at most twice by adjacent swaps, output the lexicographically largest permutation reachable.

Level: Medium6 of 10
Topics: Greedy, Array
Solved: No attempts yet

Problem

Rick wanted to test how resourceful his grandson Morty is. Morty's beloved Jessica is locked in a room behind a code lock, and Morty must pass Rick's experiment to save her.

Rick placed $n$ juice cups in a row in front of Morty. Each cup has a number from $1$ to $n$ written on it. The cup at position $i$ from the left has the number $a_i$ . All numbers are distinct, so they form a permutation of $1$ to $n$ .

Morty may swap two adjacent cups as many times as he likes. His hands shake, so each swap spills some juice from both cups. Rick allows him to touch each cup at most two times. The safe password is the lexicographically largest permutation, read from left to right, that can result from the experiment.

Help Morty find the password and save Jessica!

Input

The first line contains the integer $n$ ( $1 \le n \le 100\,000$ ), the number of cups.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le n$ ), the numbers on the cups at the start of the experiment. All $a_i$ are distinct.

Output

Print $n$ integers separated by spaces: the password.

Hint

A permutation $a$ of length $n$ is lexicographically greater than a permutation $b$ of length $n$ if there exists an $x$ such that $a_i = b_i$ for all $i$ from $1$ to $x - 1$ and $a_x > b_x$ .

Examples2

Example 1
Input
```
5
5 4 3 2 1
```
Expected output
```
5 4 3 2 1
```
Example 2
Input
```
7
7 1 2 3 4 5 6
```
Expected output
```
7 3 4 1 2 6 5
```