Cartesian Tree

Problem Description

You are given a permutation $p_1, p_2, \dots, p_n$ of $1 \sim n$.

Find a permutation $q$ of $1 \sim n$ such that for any interval $[l, r]$ ($1 \le l \le r \le n$), the position of the minimum among $p_l, p_{l+1}, \dots, p_r$ equals the position of the minimum among $q_l, q_{l+1}, \dots, q_r$.

Output the lexicographically smallest such $q$.

Input Format

The first line contains an integer $n$ ($1 \le n \le 10^6$).

The next line contains a permutation $p_1, p_2, \dots, p_n$ of length $n$.

Output Format

One line with $n$ numbers $q_1, q_2, \dots, q_n$, the lexicographically smallest permutation.

Sample Input

5
4 3 1 5 2

Sample Output

3 2 1 5 4