트리 회전 2

문제

정원사 Byteasar는 Rotatus Informatikus라는 희귀한 나무를 기르고 있다. 이 나무에는 다음과 같은 흥미로운 특징이 있다.

나무는 곧은 가지, 분기점, 그리고 잎으로 이루어진다. 땅에서 자라나는 줄기도 하나의 가지다.
각 가지의 위쪽 끝에는 분기점 또는 잎이 있다.
가지 끝의 분기점에서는 정확히 두 개의 가지, 즉 왼쪽 가지와 오른쪽 가지가 갈라져 나온다.
나무의 각 잎에는 $1$ 부터 $n$ 까지의 정수 하나가 붙어 있으며, 모든 잎의 번호는 서로 다르다.
약간의 손질로 임의의 분기점에 대해 이른바 회전을 수행할 수 있다. 회전은 그 분기점에서 갈라지는 왼쪽 가지와 오른쪽 가지를 서로 맞바꾼다.

나무의 코로나는 잎의 번호를 왼쪽에서 오른쪽으로 읽어 얻는 정수의 수열이다.

Byteasar는 단정함과 질서를 중요하게 여기며, 적절한 회전으로 나무를 얼마나 단정하게 만들 수 있을지 궁금해한다. 나무의 단정함은 코로나의 역전 수, 즉 코로나 $a_1, a_2, \ldots, a_n$ 에서 $1 \le i < j \le n$ 이면서 $a_i > a_j$ 인 쌍 $(i, j)$ 의 개수로 측정한다.

원래 나무(왼쪽)의 코로나는 $3, 1, 2$ 이며 역전이 두 개다. 한 번 회전하면 코로나가 $1, 3, 2$ 인 나무(오른쪽)가 되고, 역전은 하나뿐이다. 이 두 나무는 각각 $5$ 개의 가지를 가진다.

회전을 적절히 수행하여 얻을 수 있는 Byteasar 나무 코로나의 최소 역전 수를 구하는 프로그램을 작성하라.

입력

표준 입력의 첫 줄에는 Byteasar 나무의 잎 개수를 나타내는 정수 $n$ ( $2 \le n \le 10^6$ )이 하나 주어진다. 이어서 나무의 설명이 재귀적으로 주어진다.

줄기(나무가 자라나는 가지)의 끝에 번호 $p$ ( $1 \le p \le n$ )인 잎이 있으면, 그 나무의 설명은 정수 $p$ 하나만을 담은 한 줄로 이루어진다.
줄기의 끝에 분기점이 있으면, 그 나무의 설명은 세 부분으로 이루어진다.
- 숫자 $0$ 하나를 담은 첫 줄,
- 그다음 왼쪽 부분 나무의 설명(분기점의 왼쪽 가지를 줄기로 간주),
- 마지막으로 오른쪽 부분 나무의 설명(분기점의 오른쪽 가지를 줄기로 간주).

출력

주어진 나무에서 회전을 연속으로 수행하여 얻을 수 있는 코로나의 최소 역전 수를 정수 하나로 출력한다.

힌트

위 그림은 첫 번째 테스트의 나무를 나타내며, 그 코로나는 $3, 1, 2$ 이다.