Travel between two islands

$N$ islands numbered $1$ to $N$ stand in a row. No bridge connects them yet, so people can only travel by boat, and the government decided to build the $N-1$ bridges that join island $i$ to island $i+1$. The bridges cannot all be built at once, so they are finished one at a time in a fixed order.

Each time a bridge is finished, the government wants two values.

• The number of island pairs $(i, j)$ with $i < j$ that can reach each other.
• The sum, over those pairs, of the smallest number of bridges you have to cross to get from island $i$ to island $j$.

Report both values after every bridge.

The first line contains the number of islands $N$ ($2 \le N \le 10^5$).

Each of the next $N-1$ lines contains one integer $i$ ($1 \le i < N$), meaning that the bridge joining island $i$ and island $i+1$ is built at that turn. No number appears twice.

After each bridge is built, print the two values on one line, separated by a space. Print $N-1$ lines in total.