二叉树

时间限制:15s      空间限制:256MB

题目描述

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


输入格式

第一行n
下面每行,一个数x
如果x==0,表示这个节点非叶子节点,递归地向下读入其左孩子和右孩子的信息,
如果x!=0,表示这个节点是叶子节点,权值为x。


输出格式

一行,最少逆序对个数。


样例输入

3
0
0
3
1
2

样例输出

1

提示

对于100%的数据:2<=n<=200000。


题目来源

没有写明来源

Menuappsclose