Tree Rotations

Byteasar the gardener grows a rare tree called Rotatus Informatikus. It has a few notable properties:

• The tree is built from straight branches, bifurcations, and leaves. The trunk rising from the ground counts as a branch too.
• Each branch ends at its top in either a bifurcation or a leaf.
• Exactly two branches fork out of every bifurcation: a left branch and a right branch.
• Each leaf carries a distinct integer label from $1$ to $n$.
• A rotation may be applied to any bifurcation, swapping the left and right branches that fork out of it.

The corona of the tree is the sequence of integers read off the leaf labels from left to right.

The tree on the left has corona $3, 1, 2$ and two inversions. A single rotation yields the tree on the right, whose corona $1, 3, 2$ has just one inversion. Both trees have five branches.

The neatness of a tree is the number of inversions in its corona, that is, the number of pairs $(i, j)$ with $1 \le i < j \le n$ and $a_i > a_j$ in the corona $a_1, a_2, \dots, a_n$.

Compute the minimum number of inversions in the corona that can be reached by a sequence of rotations.

The first line contains a single integer $n$ ($2 \le n \le 200000$), the number of leaves. The description of the tree follows and is defined recursively:

• if the trunk ends in a leaf labelled $p$ ($1 \le p \le n$), the description is a single line holding the integer $p$;
• if the trunk ends in a bifurcation, the description has three parts: a line holding the single number $0$, then the description of the left subtree (treating the left branch as its trunk), then the description of the right subtree (treating the right branch as its trunk).

Print one integer: the minimum number of inversions in the corona attainable by a sequence of rotations.

The figure above shows the tree with corona $3, 1, 2$, which has two inversions; a single rotation gives corona $1, 3, 2$ with one inversion, the minimum.