逆序对(leaves)

问题描述

现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点，满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。 要求进行一系列交换，使得最终所有叶子节点的权值按照遍历序写出来，逆序对个数最少。

输入格式

第一行n表示叶子结点个数

接下来每行一个数x 如果x为0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息。 如果x不为0，表示这个节点是叶子节点，权值为x

输出格式

输出一行，最少逆序对个数。

输入样例

3
0
0
3
1
2

输出样例

1

数据范围和约定

对于$10%$的数据$n \le 20$。

对于$30%$的数据 $n \le 2000$。

对于$100%$的数据$n \le 200000$。