#include #include #include #include #include #include #define Max(a, b) ((a) > (b) ? (a) : (b)) #define Min(a, b) ((a) > (b) ? (b) : (a)) #define abs(x) ((x) > 0 ? (x) : -(x)) #define rep(i, n) for(int i = 0; i < (n); i++) #define INF 1000000000000 //10^12 #define MOD 1000000007 //10^9 + 7 #define endl printf("\n") typedef long long ll; #define MAX_N 200010 ll n, dat[2 * MAX_N - 1]; void init(ll n_) { n = 1; while (n < n_) { n *= 2; } for (int i = 0; i < 2 * n - 1; i++) { dat[i] = 0; } } void update(ll k, ll a) { k += n - 1; dat[k] += a; while (k > 0) { k = (k - 1) / 2; dat[k] = dat[2 * k + 1] + dat[2 * k + 2]; } } //[a, b)の和を求める int query(ll a, ll b, ll k, ll l, ll r) { if (r <= a || b <= l) { return 0; } if (a <= l && r <= b) { return dat[k]; } else { ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2); ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return vl + vr; } } typedef struct { ll u, v; } E; int asort(const void *a, const void *b) { E x = *(E *)a, y = *(E *)b; if (x.u > y.u) return 1; if (x.u < y.u) return -1; return 0; } ll cnt = 0; void dfs(ll i, E *e, ll *id) { update(i, 1); cnt += query(0, i, 0, 0, n); for (ll j = id[i]; j < id[i + 1]; j++) { if (dat[n - 1 + e[j].v] == 0) { dfs(e[j].v, e, id); } } update(i, -1); return; } int main(int argc, char **argv) { ll m; scanf("%lld", &m); E e[200010]; ll a; for (int i = 1; i < m; i++) { scanf("%lld", &a); e[i - 1].u = a; e[i - 1].v = i; } qsort(e, m - 1, sizeof(E), asort); ll id[200010]; id[0] = 0; ll p = 0; for (ll i = 0; i < m; i++){ while(e[p].u < i && p < m - 1) p++; id[i] = p; } id[m] = m - 1; init(m); dfs(0, e, id); printf("%lld\n", cnt); return 0; }