Description

One day, on a whim, Hz blew $n$ different bubbles to play with (guaranteed to be no duplicates). Because he still has homework to do, he asks you to help sort these bubbles into a tree and output its postorder traversal.

Specifically, Hz uses the binary search tree (BST) algorithm to insert the bubbles into the tree in the given order. Each insertion adds the new bubble as a leaf, and the in-order traversal of the whole tree remains in ascending order.

The binary tree after all insertions is the required tree.

Input Format

A total of $2$ lines.

• The first line contains $1$ integer $n$.
• The second line contains $n$ integers, where the $i$-th integer $a_i$ is the size of the $i$-th bubble.

Output Format

A total of $n+1$ lines.

• The first line outputs the depth of the tree.
• Then output $n$ lines, one integer per line, giving the postorder traversal of the tree.

8
1 4 3 9 10 35 2 7

deep=5
2
3
7
35
10
9
4
1

Hint

• This problem has two subtasks. The first subtask has $10$ test points, each worth $5$ points. The second subtask has $5$ test points, each worth $10$ points.
• Constraints: $1 \le n \le 3 \times 10^5$, $1 \le a_i \le 10^9$, and all $a_i$ are distinct.

Translated by ChatGPT 5