트리 회전

정원사 바이테아사르는 로타투스 인포르마티쿠스라는 희귀한 나무를 기른다. 이 나무에는 몇 가지 독특한 성질이 있다.

• 나무는 곧은 가지, 갈래, 잎으로 이루어진다. 땅에서 자라난 줄기도 하나의 가지다.
• 모든 가지의 윗끝은 갈래이거나 잎이다.
• 갈래에서는 정확히 두 개의 가지, 즉 왼쪽 가지와 오른쪽 가지가 뻗어 나온다.
• 각 잎에는 $1$부터 $n$까지의 정수 라벨이 서로 겹치지 않게 하나씩 붙어 있다.
• 임의의 갈래에 회전을 수행할 수 있으며, 회전하면 그 갈래에서 뻗어 나온 왼쪽 가지와 오른쪽 가지가 서로 바뀐다.

나무의 코로나는 잎의 라벨을 왼쪽에서 오른쪽으로 읽어 얻는 정수 수열이다.

왼쪽 나무의 코로나는 $3, 1, 2$이고 역위(inversion)가 두 개다. 한 번 회전하면 오른쪽 나무가 되며, 코로나 $1, 3, 2$의 역위는 한 개뿐이다. 두 나무 모두 가지가 다섯 개다.

나무의 정돈도는 코로나의 역위 개수, 즉 코로나 $a_1, a_2, \dots, a_n$에서 $1 \le i < j \le n$이면서 $a_i > a_j$인 쌍 $(i, j)$의 개수로 정의한다.

회전을 여러 번 수행하여 얻을 수 있는 코로나의 최소 역위 개수를 구하라.

첫째 줄에 잎의 개수를 나타내는 정수 $n$ ($2 \le n \le 200000$)이 주어진다. 이어서 나무의 설명이 재귀적으로 주어진다.

• 줄기의 끝이 라벨 $p$ ($1 \le p \le n$)인 잎이면, 설명은 정수 $p$ 하나가 적힌 한 줄이다.
• 줄기의 끝이 갈래이면, 설명은 세 부분으로 이루어진다. 먼저 숫자 $0$ 하나가 적힌 줄이 오고, 그다음 왼쪽 부분나무의 설명(왼쪽 가지를 줄기로 간주)이, 마지막으로 오른쪽 부분나무의 설명(오른쪽 가지를 줄기로 간주)이 온다.

회전을 여러 번 수행하여 얻을 수 있는 코로나의 최소 역위 개수를 정수 하나로 출력한다.

위 그림은 코로나가 $3, 1, 2$인 나무를 나타낸다. 이 나무는 역위가 두 개이며, 한 번 회전하면 코로나가 $1, 3, 2$가 되어 역위가 한 개인 최솟값에 이른다.