南极的科学家们发现了一个新物种！他们提取了一个样本并将其带回实验室进行测试。

他们很快注意到该物种繁殖非常频繁，且繁殖只需要一个亲本。然而，在亲本繁殖两次后，它就会变得不育，无法再次繁殖。

尽管如此，实验室里的标本数量还是激增，因此需要建立家谱。

他们决定使用简单的文本编辑器，按照以下约定绘制家谱树： 标本的名字将被写在由字符 '-'、'|' 和 'o' 组成的精美方框内。上下边框的中心点将用字符 '+' 标记。如果边框长度为偶数，'+' 将位于两个中心点中的左侧。

o--+--o
|anton|
o--+--o
o----+----o
|anamarija|
o----+----o
o-+--o
|pero|
o-+--o

方框将通过连接线连接。一条连接线在其各自的 '+' 字符处连接两个或多个方框，亲本标本放置在其子代上方。方框和连接线不得重叠。

  +
  |
  o
  |
  +
  +
  |
o---o---o
|   |
+   +
  +
  |
o-----o-----o
|     |
+     +

如果亲本有一个孩子，则使用点对点（最左侧示例）连接。如果亲本有两个孩子，则使用分支连接，年长的孩子在左侧，年幼的孩子在右侧。

分支连接可以在水平方向上扩展，只要两侧的 '-' 字符数量保持相等即可。连接线不能在垂直方向上扩展。

不用担心，你不需要画出这棵树，只需要确定绘制它所需的字符总数。空格字符不计入，仅计算 '-'、'|'、'+'、'o' 以及名字中的字母。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 300\,000$)，表示实验室中标本的数量。

标本按出生顺序标记为 $1$ 到 $N$，最年长的标记为 $1$，最年轻的标记为 $N$。

接下来的 $N$ 行包含所有标本按出生顺序排列的出生记录。每个标本（第一个亲本未知的标本除外）由以下两条信息描述： $name$ - 最多 $20$ 个小写英文字母组成的序列 $parent$ - 一个整数，表示该标本的亲本

输出格式

输入的第一行也是唯一一行应包含绘制家谱树所需的最小字符总数。

子任务

测试数据中 $N < 30$ 的部分分值为 $50$ 分。 测试数据中 $N < 3000$ 的部分分值为 $75$ 分。

样例

样例输入 1

3
adam
kain 1
abel 1

样例输出 1

64

样例输入 2

12
anton
ana 1
luka 1
mia 2
tea 3
jakov 3
semiramida 5
dominik 5
anamarija 4
eustahije 4
lovro 2
lovro 11

样例输出 2

371

说明

计算字符数得到 $64$ 和 $371$。