Travel between two islands

Interview

Time limit1sMemory limit16 MB

Summary

After each bridge joins two neighboring islands, report how many island pairs are mutually reachable and the total bridge crossings summed over those pairs.

Level: Medium5 of 10
Topics: Union-find, Math
Solved: No attempts yet

Problem

$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.

Input

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.

Output

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

Examples5

Example 1
Input
```
3
1
2
```
Expected output
```
1 1
3 4
```
Example 2
Input
```
2
1
```
Expected output
```
1 1
```
Example 3
Input
```
4
1
2
3
```
Expected output
```
1 1
3 4
6 10
```
Example 4
Input
```
4
3
2
1
```
Expected output
```
1 1
3 4
6 10
```
Example 5
Input
```
5
2
3
1
4
```
Expected output
```
1 1
3 4
6 10
10 20
```