8229: [yosupo] Tree - Cartesian Tree
[Creator : ]
Description
You are given a sequence $A = (a_0, a_1, \dots, a _ {N-1})$ of distinct integers.Construct the Cartesian tree derived from this sequence $A$.
The smallest element becomes the root.
The smallest element becomes the root.
Input
$N$
$a_0$ $a_1$ ... $a _ {N - 1}$
$a_0$ $a_1$ ... $a _ {N - 1}$
Output
$p_0$ $p_1$ $p_2$ ... $p_{N - 1}$
$p_i$ is the parent of vertex $i$. $p_r = r$ for the root node $r$ of the tree.
$p_i$ is the parent of vertex $i$. $p_r = r$ for the root node $r$ of the tree.
Constraints
$1 \leq N \leq 10^6$
$0 \leq a_i \leq 10^9$
$i \ne j$ implies $a_i \ne a_j$
all values are integers
$0 \leq a_i \leq 10^9$
$i \ne j$ implies $a_i \ne a_j$
all values are integers
Sample 1 Input
3
1 0 2
Sample 1 Output
1 1 1
Sample 2 Input
11
9 3 7 1 8 12 10 20 15 18 5
Sample 2 Output
1 3 1 3 10 6 4 8 6 8 3