#include using namespace std; struct EulerTour{ // オイラーツアー vector tour; // 各頂点番号に対する、tourの最左/最右の位置 vector L, R; EulerTour(){} EulerTour(int N, vector G[], int root=0){ initialize(N, G, root); } void dfs(int i, int p, vector G[]){ L[i] = tour.size(); tour.push_back(i); for(int j : G[i]) if(j != p){ dfs(j, i, G); tour.push_back(i); } R[i] = tour.size()-1; } void initialize(int N, vector G[], int root){ L.resize(N); R.resize(N); dfs(root, -1, G); } }; template struct BIT { int n; vector dat; BIT(int n=0){ initialize(n); } void initialize(int nin){ n = nin; dat.resize(n, 0); } T sum(int i){ T s = 0; while(i >= 0){ s += dat[i]; i = (i & (i+1)) - 1; } return s; } T sum_between(int i, int j){ return sum(j) - sum(i-1); } void plus(int i, T x){ while(i < n){ dat[i] += x; i |= i+1; } } // a[0]+...+a[ret] >= x int lower_bound(T x){ int ret = -1; int k = 1; while(2*k <= n) k <<= 1; for( ;k>0; k>>=1){ if(ret+k < n && dat[ret+k] < x){ x -= dat[ret+k]; ret += k; } } return ret + 1; } }; vector child[200000]; int main(){ int N; cin >> N; for(int i=1; i> a; child[a].push_back(i); } EulerTour et(N, child, 0); int len = et.tour.size(); BIT bit(len); int64_t ans = 0; for(int i=N-1; i>=0; i--){ ans += bit.sum_between(et.L[i], et.R[i]); bit.plus(et.L[i], 1); } cout << ans << endl; return 0; }