두 섬 사이의 이동

$1$번부터 $N$번까지 번호가 붙은 섬 $N$개가 일렬로 늘어서 있다. 섬 사이에 다리가 없어서 배로만 오갈 수 있었기에 정부는 섬 $i$와 섬 $i+1$을 잇는 다리를 $N-1$개 짓기로 했다. 다리를 한 번에 다 지을 수는 없으므로 정해진 순서대로 하나씩 완성한다.

다리가 하나 완성될 때마다 정부는 다음 두 값을 알고 싶어 한다.

• 서로 오갈 수 있는 섬 쌍 $(i, j)$ ($i < j$)의 개수
• 그런 쌍마다 섬 $i$에서 섬 $j$까지 가는 데 건너야 하는 최소 다리 개수를 모두 더한 값

정부가 원하는 두 값을 다리가 완성되는 순간마다 구하라.

첫째 줄에 섬의 개수 $N$ ($2 \le N \le 10^5$)이 주어진다.

다음 $N-1$개 줄에는 각 줄마다 정수 $i$ ($1 \le i < N$)가 하나씩 주어진다. 이는 섬 $i$와 섬 $i+1$을 잇는 다리를 그 차례에 짓는다는 뜻이다. 같은 수가 두 번 주어지는 경우는 없다.

다리를 하나 지을 때마다 위의 두 값을 공백으로 구분해 한 줄에 출력한다. 모두 $N-1$개 줄을 출력한다.