SWERC 组织者想要举办一场美食活动。

活动地点是一栋拥有 $n$ 个房间的建筑，这些房间由 $n-1$ 条走廊连接（每条走廊连接两个房间），使得从任何一个房间都可以到达其他任何房间。

在每个房间里，你都需要安排一道典型的意大利菜品进行品鉴。你可以从 $n$ 道典型的意大利菜品中进行选择，这些菜品的评分从 $1$ 到 $n$ 不等，取决于它们的美味程度（$n$ 为最高评分）。这 $n$ 道菜品的评分各不相同。

你希望将这 $n$ 道菜分配到 $n$ 个房间中，使得“愉悦之旅”的数量最大化。所谓“愉悦之旅”是指一个非空的房间序列，满足：

• 序列中的每个房间都通过走廊与序列中的下一个房间相连。
• 房间内菜品的评分（按序列给出的顺序）是递增的。

如果你以最优方式分配这 $n$ 道菜，那么“愉悦之旅”的最大数量是多少？

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 1\,000\,000$)，表示房间的数量。

第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$)。每个 $p_i$ 表示房间 $i$ 和房间 $p_i$ 之间有一条走廊。保证该建筑满足从任何一个房间都可以到达其他任何房间的性质。

输出格式

输出“愉悦之旅”的最大数量。

样例

样例输入 1

5
1 2 2 2

样例输出 1

13

说明

样例 1 的说明： 将评分 1 的菜品放在房间 1，评分 2 的菜品放在房间 3，评分 3 的菜品放在房间 2，评分 4 的菜品放在房间 5，评分 5 的菜品放在房间 4 是最优的。 所有 13 种可能的愉悦之旅为：(1), (2), (3), (4), (5), (1, 2), (3, 2), (2, 4), (2, 5), (1, 2, 4), (1, 2, 5), (3, 2, 4), (3, 2, 5)。 也存在其他分配菜品的方式使得愉悦之旅的数量达到 13。

样例输入 2

10
1 2 3 4 3 2 7 8 7

样例输出 2

47