笛卡尔树

题目描述

给你一个 $1\sim n$ 的排列 $p_1, p_2, \dots, p_n$。

让你找到一个 $1\sim n$ 的排列 $q$，满足对于任意区间 $[l, r] (1\leq l\leq r\leq n)$，满足 $p_{l}, p_{l+1}, \dots, p_r$ 中的最小值的位置，和 $q_{l}, q_{l+1}, \dots, q_r$ 的最小值的位置相同。

输出满足条件的字典序最小的 $q$。

输入格式

第一行一个整数 $n(1\leq n\leq 10^6)$。

接下来一行，一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$。

输出格式

一行 $n$ 个数 $q_1, q_2, \dots, q_n$，表示这个字典序最小的排列。

样例输入

5
4 3 1 5 2

样例输出

3 2 1 5 4