Description

You are given a binary tree with $n$ leaves. Each leaf has a weight $p_i$ (note: the root is not a leaf), and the weights of all leaves form a permutation of $1 \sim n$.
For any node in this binary tree, it is guaranteed that it is either a leaf, or it has both left and right children.
You may choose any set of nodes and swap their left and right subtrees.
On the final tree, perform a preorder traversal of the whole tree and record the weights of the encountered leaves to form a permutation of length $n$. You need to minimize the number of inversions of this permutation.

Input Format

The first line contains an integer $n$, the number of leaves.
In the following lines, the tree is read recursively. When reading any subtree, start with its root. For a node $u$, first read an integer $x$ on a separate line.

• If $x \neq 0$, then $u$ is a leaf and its weight is $x$.
• If $x = 0$, then $u$ is an internal node; next read the information of its left subtree, and then the information of its right subtree.

Output Format

Output a single integer, the minimal number of inversions.

3
0
0
3
1
2

1

Hint

Explanation for Sample 1:

In the figure below, the left is the initial tree, and the right is the tree after the operations.

Constraints:

• For $30\%$ of the testdata, $n \leq 5 \times 10^3$.
• For $100\%$ of the testdata, $2 \leq n \leq 2 \times 10^5$, $0 \leq x \leq n$, and the weights of all leaves form a permutation of $1 \sim n$.

Note: Please note that $n$ is not the number of nodes in the tree.

Translated by ChatGPT 5