Example

Input

4
1 1 2


Output

6
#include<iostream>
#include<algorithm>
#include<cstdio> 
#include<cstring>
#include<cmath>
#include<map>
#include<queue> 
#include<vector>
using namespace std;
vector<int> a[110000];
int n,f[110000],d[110000],p,i,tt,o,ff[110000][30],b[110000],pp,tot; 
long long ans;
void dfs(int x) {
	int p = a[x].size();
	for (int i = 0; i < p; i++) {
		d[a[x][i]] = d[x] + 1;
		ff[a[x][i]][0] = x;
		dfs(a[x][i]);
	}
}
void init()
{
  int i,j;
  //p[i][j]表示i?点的第2^j祖先
  for(j=1;(1<<j)<=n;j++)
    for(i=1;i<=n;i++)
      if(ff[i][j-1]!=-1)
        ff[i][j]=ff[ff[i][j-1]][j-1];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先
}
int lca(int a,int b)//最近公共祖先
{
  int i,j;
  if(d[a]<d[b])swap(a,b);
  for(i=0;(1<<i)<=d[a];i++);
  i--;
  //使a，b?点的深度相同
  for(j=i;j>=0;j--)
    if(d[a]-(1<<j)>=d[b])
      a=ff[a][j];
  if(a==b)return a;
  //倍?法，?次向上?深度2^j，找到最近公共祖先的子?点
  for(j=i;j>=0;j--)
  {
    if(ff[a][j]!=-1&&ff[a][j]!=ff[b][j])
    {
      a=ff[a][j];
      b=ff[b][j];
    }
  }
  return ff[a][0];
}
int main() {
	scanf("%d", &n);
	for (i = 2; i <= n; i++) {
		scanf("%d", &f[i]);
		a[f[i]].push_back(i);
	}
	for (i = 1; i <= n; i++) sort(a[i].begin(), a[i].end());
	//for (i = 0; i < a[2].size(); i++) cout<<a[2][i]<<" ";cout<<endl;
	d[1] = 0;
	dfs(1);
	queue<int> q;
	while (!q.empty()) q.pop();
	q.push(1); 
	while (!q.empty()) {
		int p = q.front();  q.pop();
		b[++pp] = p;
		int pp = a[p].size();
		for (int i = 0; i < pp; i++) {
			q.push(a[p][i]); 
		}
	}
	init(); ff[1][0] = -1;
	ans = 0;
	//for (i = 1; i <= pp; i++) cout<<b[i]<<" "; cout<<endl;
	for (i = 1; i < pp; i++) {
		p = lca(b[i], b[i + 1]);
		tot = (d[b[i]] - d[p]) + (d[b[i + 1]] - d[p]);
		ans = ans + tot;
	}
	printf("%lld\n", ans);
}