笛卡尔树（Cartesian Tree）

问题描述

给定一个由 $N$ 个互异整数组成的序列 $A = (a_0, a_1, \dots, a_{N-1})$ 。
构造该序列的笛卡尔树（Cartesian Tree）：

树中每个节点对应序列中的一个元素；
树的根是序列中最小值对应的元素；
对于任意节点 $i$ ，其左子树对应 $i$ 左侧、且在“下一个更小值”范围内的子序列，右子树对应右侧同理；
形式上：若 $i$ 是区间 $[l, r]$ 中最小值的位置，则其左孩子是 $[l, i-1]$ 中最小值对应节点，右孩子是 $[i+1, r]$ 中最小值对应节点。

输出该树的父节点数组： $p_0, p_1, \dots, p_{N-1}$ ，其中 $p_i$ 表示顶点 $i$ 的父节点编号；根节点 $r$ 满足 $p_r = r$ 。

$N$
$a_0\ a_1\ \cdots\ a_{N-1}$

$p_0\ p_1\ \cdots\ p_{N-1}$

其中 $p_i$ 是顶点 $i$ 的父节点编号；根节点 $r$ 满足 $p_r = r$ 。

3
1 0 2

1 1 1

11
9 3 7 1 8 12 10 20 15 18 5

1 3 1 3 10 6 4 8 6 8 3