园丁 Byteasar 正在培育一种名为 Rotatus Informatikus 的珍稀树木。它具有以下有趣的特征：

• 这棵树由笔直的树枝、分叉点和叶子组成。从地面长出的树干也是一根树枝。
• 每根树枝的顶端要么是一个分叉点，要么是一片叶子。
• 从分叉点处会分出两根树枝——左树枝和右树枝。
• 树的每片叶子上都标有一个 $1 \ldots n$ 范围内的整数。叶子的标签是唯一的。
• 通过园艺工作，可以在任何分叉点上执行所谓的“旋转”操作，即交换从该分叉点分出的左树枝和右树枝。

树的“冠部序列”是指从左到右读取叶子标签所得到的整数序列。

Byteasar 来自古老的 Byteburg 镇，像所有真正的 Byteburg 人一样，他崇尚整洁和秩序。他想知道通过适当的旋转，他的树能变得多么整洁。树的整洁度通过其冠部序列中的逆序对数量来衡量，即在冠部序列 $a_{1}, a_{2}, \ldots, a_{n}$ 中，满足 $1 \le i < j \le n$ 且 $a_{i} > a_{j}$ 的数对 $(i, j)$ 的数量。

原始树（左侧）的冠部序列为 3,1,2，有两个逆序对。进行一次旋转后得到的树（右侧）冠部序列为 1,3,2，仅有一个逆序对。这两棵树各有 5 根树枝。

编写一个程序，确定通过旋转操作，Byteasar 的树的冠部序列中可能达到的最小逆序对数量。

输入格式

标准输入的第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)，表示 Byteasar 树中叶子的数量。接下来是树的描述。树的定义是递归的：

• 如果树干末端是一片标有 $p$ ($1 \le p \le n$) 的叶子，则树的描述由包含单个整数 $p$ 的一行组成；
• 如果树干末端是一个分叉点，则树的描述由三部分组成：
  • 第一行包含一个数字 $0$；
  • 接着是左子树的描述（如同左树枝是其树干一样）；
  • 最后是右子树的描述（如同右树枝是其树干一样）。

在至少占 30% 分值的测试中，满足 $n \le 5\,000$。

输出格式

在标准输出的第一行（也是唯一一行）打印一个整数：通过一系列旋转操作，树的冠部序列中可能达到的最小逆序对数量。

样例

输入 1

3
0
0
3
1
2

输出 1

1

图 1 展示了样例中给出的树。