Example

Input

4
1 1 2


Output

6
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cassert>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<deque>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;
typedef long long ll;
#define MAX 200010
#define IINF INT_MAX
int n, par[MAX];
vector<int> G[MAX];

typedef pair<int,int> ii;

//RMQ LCA ------------------------------- begin
class LCA_RMQ{
private:
  int limit,N;
  vector<ii> dat;
public:
  void init(int n_){
    N = n_;
    dat.clear();
    limit = 1;
    while(limit<n_)limit*=2;
    dat.resize(2*limit);
    for(int i=0;i<2*limit-1;i++) dat[i] = ii(IINF,IINF);//ii(depth,index)
  }

  ii _build(int cur,int L,int R,const vector<ii> &buf){
    if( !( 0 <= cur && cur < 2*limit ) ) return ii(IINF,IINF);
    if( L == R-1 ) {
      if( L >= N ) return ii(IINF,IINF);
      dat[cur] = buf[L];
    } else {
      ii vl = _build(cur*2+1,L,(L+R)/2,buf);
      ii vr = _build(cur*2+2,(L+R)/2,R,buf);
      dat[cur] = min(vl,vr);
    }
    return dat[cur];
  }

  void build(const vector<ii> &buf){ _build(0,0,limit,buf); };
 
// k????????????(0-indexed)???a????????´
  void update(int k,ii a){
    k += limit-1;
    dat[k] = a;
    while(k > 0){
      k = (k-1)/2;
      dat[k] = (dat[k*2+1].first>dat[k*2+2].first?dat[k*2+2]:dat[k*2+1]);
    }
  }
 
  ii _query(int a,int b,int k,int l,int r){
    if(r<=a || b<=l)return ii(IINF,-1);
    else if(a<=l && r<=b)return dat[k];
     
      ii vl = _query(a,b,k*2+1,l,(l+r)/2);
      ii vr = _query(a,b,k*2+2,(l+r)/2,r);

      return min(vl,vr);
  }

  ii query(int a,int b){ return _query(a,b,0,0,limit); }
};

int root;
vector<int> id,vs,depth;


void LCA_dfs(int v,int p,int d,int &k){
  id[v] = k;
  vs[k] = v;
  depth[k++] = d;
  for(int i=0;i<(int)G[v].size();i++){
    if(G[v][i] != p){
      LCA_dfs(G[v][i],v,d+1,k);
      vs[k] = v;
      depth[k++] = d;
    }
  }
}

void LCA_init(int V,LCA_RMQ &rmq){
  root = 0;
  vs.clear();
  vs.resize(V*2,0);
  depth.clear();
  depth.resize(V*2,0);
  id.clear();
  id.resize(V);
  int k = 0;
  LCA_dfs(root,-1,0,k);
  rmq.init(k+1);  
  vector<ii> tmp;
  rep(i,k) tmp.push_back(ii(depth[i],vs[i]));
  rmq.build(tmp);
}

int lca(int u,int v,LCA_RMQ &rmq){ return rmq.query(min(id[u],id[v]),max(id[u],id[v])+1).second; }

//RMQ LCA ------------------------------- end

vector<int> to[MAX];
int i_th_vertex[MAX];
int score[MAX];

void compute() {
  rep(i,n) sort(to[i].begin(),to[i].end());
  LCA_RMQ rmq;
  LCA_init(n,rmq);
  {
    deque<int> deq;
    deq.push_back(0);
    score[0] = 0;
    int ptr = 0;
    while( deq.size() ) {
      int cur = deq.front(); deq.pop_front();
      i_th_vertex[ptr++] = cur;
      rep(i,(int)to[cur].size()) {
	int next = to[cur][i];
	assert( score[next] == 0 );
	score[next] = score[cur] + 1;
	deq.push_back(next);
      }
    }
  }
  long long answer = 0;
  rep(i,n-1) {
    int s = i_th_vertex[i];
    int t = i_th_vertex[i+1];
    int node = lca(s,t,rmq);
    answer += (ll)( (ll)abs(score[s]-score[node]) + (ll)abs(score[node]-score[t]) );
  }
  cout << answer << endl;
}

int main() {
  if(0) {
    n = 100000;
    cout << n << endl;
    rep(i,n-1) {
      if( i ) printf(" ");
      cout << 1;
    } puts("");
    return 0;
  }

  cin >> n;
  rep(i,n-1) {
    cin >> par[i+1];
    --par[i+1];
    G[par[i+1]].push_back(i+1);
    G[i+1].push_back(par[i+1]);
    to[par[i+1]].push_back(i+1);
  }
  compute();
  return 0;
}