Rotacje na drzewie 2

Limit pamięci: 128 MB

Niniejsze zadanie to trudniejsza wersja zadania Rotacje na drzewie z II etapu XVIII OI. Nie wystąpiła ona w samym konkursie.

Ogrodnik Bajtazar zajął się hodowlą rzadkiego drzewa o nazwie Rotatus Informatikus. Ma ono bardzo ciekawe własności:

• Drzewo składa się z prostych gałęzi, rozgałęzień i liści. Wyrastający z ziemi pień drzewa jest również gałęzią.
• Każda gałąź jest zakończona u góry rozgałęzieniem lub liściem.
• Z rozgałęzienia na końcu gałęzi wyrastają dokładnie dwie dalsze gałęzie - lewa i prawa.
• Każdy liść drzewa zawiera jedną liczbę całkowitą z zakresu . Liczby w liściach nie powtarzają się.
• Za pomocą pewnych zabiegów ogrodniczych, dla dowolnego rozgałęzienia można wykonać tzw. rotację, czyli zamienić miejscami lewą i prawą gałąź.

Bajtazar pochodzi ze starego miasta Bajtogrodu i jak wszyscy jego mieszkańcy bardzo lubi porządek. Zastanawia się, jak za pomocą rotacji jak najlepiej uporządkować swoje drzewo. Uporządkowanie drzewa mierzymy liczbą inwersji zawartych w jego koronie, tj. dla korony wyznaczamy liczbę takich par , , dla których .

Rys. 1. Oryginalne drzewo (po lewej) o koronie zawiera dwie inwersje. Po rotacji otrzymujemy drzewo (po prawej) o koronie , które zawiera tylko jedną inwersję. Każde z tych drzew ma 5 gałęzi.

Napisz program, który wyznaczy minimalną liczbę inwersji zawartych w koronie drzewa, które można otrzymać za pomocą rotacji wyjściowego drzewa Bajtazara.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę liści drzewa Bajtazara. W kolejnych wierszach znajduje się opis drzewa. Drzewo definiujemy rekurencyjnie:

• jeśli na końcu pnia (czyli gałęzi, z której wyrasta drzewo) znajduje się liść z liczbą całkowitą (), to opis drzewa składa się z jednego wiersza zawierającego jedną liczbę całkowitą - ,
• jeśli na końcu pnia znajduje się rozgałęzienie, to opis drzewa składa się z trzech części:
  • pierwszy wiersz opisu zawiera jedną liczbę ,
  • po tym następuje opis lewego poddrzewa (tak, jakby lewa gałąź wyrastająca z rozgałęzienia była jego pniem),
  • a następnie opis prawego poddrzewa (tak, jakby prawa gałąź wyrastająca z rozgałęzienia była jego pniem).

Wyjście

W jedynym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą: minimalną liczbę inwersji w koronie drzewa, które można otrzymać za pomocą jakiegoś ciągu rotacji wyjściowego drzewa.

Przykład

Dla danych wejściowych:

3
0
0
3
1
2

poprawną odpowiedzią jest:

1

Wyjaśnienie do przykładu: Rysunek 1 ilustruje drzewo z przykładu.

Autorzy zadania: Tomasz Kociumaka, Tomasz Waleń.