Cartesian Tree

AC一覧

Problem Statement
問題文

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.

長さ $N$ の distinct な数列 $A = (a_0, a_1, \dots, a _ {N-1})$ が与えられる。 この数列 $A$ から誘導される Cartesian tree を求めよ。 ただし、最も小さい要素が根である。

Constraints
制約

Input
入力

$N$
$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$ は頂点 $i$ の親である。また、根である頂点 $r$ については $p_r = r$ とすること。

Sample
サンプル

# 1

3
1 0 2
1 1 1

# 2

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

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions