მებაღე ბაიტაზარს მოჰყავს ხე სახელად, Rotatus Informatikus, რომელსაც საინტერესო თვისებები აქვს: 

◦        ხე შედგება სწორი ტოტების, ფოთლებისა და განშტოებებისგან. მიწიდან ამოშვერილი ფესვებიც ტოტებია.

◦         ყველა ტოტი მთავრდება განშტოებით ან ფოთლით.

◦         ტოტის ბოლოში განშტოებისგან ზუსტად ორი რტო გამოდის, მარცხენა ტოტი და მარჯვენა ტოტი.

◦        ხის ყველა ფოთოლი გადანომრილია უნიკალური მთელი რიცხვით i. 1 <= i <= n (n არის ფოთლების რაოდენობა);

◦        ბაღში შესაძლებელია სხვადასხვა სამუშაოების ჩატარება, რომელსაც ეწოდება როტაცია (ბრუნვა). როტაცია შესაძლებელია ჩატარდეს ნებისმიერ განშტოებაზე და გულისხმობს, განშტოების მარცხენა და მარჯვენა ნაწილისთვის ადგილების გაცვლას.

ხის გვირგვინი ეწოდება მთელი რიცხვების მიმდევრობას, რომლის გაგებაც ფოთლების ნომრების მარცხნიდან მარჯვნივ წაკითხვით შეგვიძლია.

ბაიტაზარი წარმოშობით არის ტრადიციული ქალაქი ბაიტბურგიდან. ყველა ნამდვილი ბაიტბურგელის მსგავსად ბაიტაზარისთვის დალაგებულობასა და სისუფთავეს დიდი მნიშვნელობა აქვს. მისთვის მნიშვნელოვანია გაიგოს თუ მისი ხე რამდენად სუფთა შეიძლება გახდეს როტაციების შედეგად. ხის სისუფთავე განისაზღვრება მის გვირგვინში არსებული ინვერსიებით. სხვა სიტყვებით, ინვერსია არის ისეთი წყვილების (i , j ) რაოდენობა, რომელთათვისაც სრულდება შემდეგი პირობა 1 <= i < j <= n  და ai > aj   სადაც  a1, a2, a3 ….. an. არის ხის გვირგვინში შემავალი რიცხვები.

 ნახაზი იხილე ლინკზე: https://szkopul.edu.pl/problemset/problem/OELzSaMp2K7WAgCzcYYaKI1b/site/?key=statement

მაგალითად მარცხნივ მყოფი ხის გვირგვინი არის (3, 1, 2), რომელსაც აქვს 2 ინვერსია. ერთი როტაციით კი მისი გვირგვინი გახდა (1, 3, 2), შესაბამისად 1 ინვერსიით. თითოეულ ხეს აქვს ხუთი ტოტი.

თქვენი მიზანია, დაწეროთ პროგრამა, რომელიც განსაზღვრავს გადმოცემულ ხეში მინიმალური ინვერსიების რაოდენობას, რომელიც მიიღება როტაციების გამოყენებით . 

 შემავალი მონაცემები: პირველ ხაზში გადმოგეცემათ n ( 2 <= n <= 200 000), რომელიც განსაზღვრავს ფოთლების რაოდენობას ბაიტაზარის ხეში, ამას მოსდევს ხის აღწერა რომელიც გადმოგეცემათ რეკურსიულად.

◦         თუ მიმდინარე ტოტის ბოლოში არის ფოთოლი, ნომრით p (1 <= p <= n), მაშინ გადმოცემათ ერთი ცალი ინტეჯერი p, ფოთლის ნომერი.

◦         თუ მიმდინარე ტოტი იყოფა:

▪         პირველ ხაზში წერია 0.

▪         შემდეგ ხაზში განშტოების მარცხენა ნაწილის აღწერა.

▪         და ბოლოს განშტოების მარჯვენა ნაწილის აღწერა.

ტესტების 30% ში n <= 5000.

 გამოსატანი მონაცემები:  ერთი ხაზი. მთელი რიცხვი, რომელიც განსაზღვრავს მინიმალური ინვერსიების რაოდენობას, რომელიც როტაციებით მიიღწევა.

მაგალითები

შესატანი მონაცემები
3
0
0
3
1
2
                  დაკოპირება

გამოსატანი მონაცემები
1
                  დაკოპირება

შენიშვნა

მაგალითის ახსნა: სურათზე მოცემული მარცხენა ხის ნახაზი ზუსტად ასახავს მაგალითს.

თარგმნა: დ.გორგაძემ.