题目描述

Maria 得到了一棵树，共有 $n$ 个顶点，根为顶点 $1$。

她定义一次“对顶点区间 $[l, r]$ 的树探索”如下：对于每个编号满足 $l \le u \le r$ 的顶点，她会标记该顶点以及它的整棵子树。一个顶点可以被标记多次，也可以完全不被标记。

一次探索的结果定义为：在所有标记完成后，被标记的顶点个数。

请你帮助 Maria 编写程序 tree，求出这棵树所有可能探索结果之和。

在给示意图中，对区间 $[4, 5]$ 进行探索时：

• 区间中的顶点会被直接标记；
• 顶点 $2$ 和 $3$ 会被标记，因为它们在顶点 $5$ 的子树中；
• 顶点 $6$ 会被标记，因为它在顶点 $4$ 的子树中。

输入格式

第一行输入整数 $n$，表示树中顶点个数。

第二行输入 $n-1$ 个整数 $p_2, p_3, \dots, p_n$，其中 $p_i$ 表示顶点 $i$ 的父亲。

输出格式

输出一个整数，表示 Maria 可以进行的所有探索结果之和。

数据范围

• $1 \le n \le 10^5$
• 对于 $i=2,3,\dots,n$，有 $1 \le p_i \le n$
• 输入保证给出的是一棵树

说明

• 顶点 $u$ 的子树，指所有满足“从 $1$ 到 $v$ 的路径经过 $u$”的顶点 $v$ 所构成的集合。
• 完全二叉树（原题中的 “perfect binary tree”）指：除叶子外每个顶点都有两个直接儿子，且所有叶子到根的距离相同。

子任务

只有当某个子任务中的所有测试都通过时，才能获得该子任务的分数。

样例 1

输入

6
5 5 1 1 4

输出

87

解释

这里给出的正是题面中的示例树。

样例 2

输入

6
1 1 2 2 3

输出

82

解释

这棵树满足子任务 3 的额外限制：每个顶点的父亲编号都严格小于该顶点编号。

样例 3

输入

7
7 7 6 6 1 1

输出

120

解释

这棵树满足子任务 4 的额外限制。注意，此时对顶点编号本身没有额外限制。