Maximum Spanning Tree Weight of Tree Metric

We are given a tree \(T\) with all edge weights equal to 1. The generating graph \(G\) of \(T\) is defined as the complete undirected graph on the vertices of \(T\) where the weight of an edge connecting vertices \(i\) and \(j\) is the distance between \(i\) and \(j\) in \(T\) (i.e. the number of edges on the unique path joining them).

Let \(f(T)\) be defined as the sum of the edge weights in a maximum spanning tree of \(G\), i.e., \[ f(T)=\sum_{e\in MST(G)}w(e), \] where the edge weights \(w(e)\) are given by the distances in \(T\).

You start with a tree \(T\) that has only a single node labeled \(1\). Then there will be \(q\) operations. In each operation a new leaf is attached to an existing vertex. The new nodes get labels \(2,3,\dots,q+1\) in the order of addition. For every state of \(T\) (the initial tree and after each operation), output \(f(T)\).

Note. The distance between any two vertices is defined as the number of edges on the unique simple path connecting them.

inputFormat

The first line contains a single integer \(q\) \((1 \le q \le \text{small})\), indicating the number of operations.

Each of the next \(q\) lines contains a single integer \(p\) \((1 \le p \le current\ number\ of\ nodes)\) indicating that a new leaf is attached to node \(p\).

Initially, the tree consists of only node 1.

outputFormat

Output \(q+1\) lines. The first line is the value of \(f(T)\) for the initial tree. Then, after each operation, output the updated value of \(f(T)\).

sample

3
1
1
2

0
1
3
7