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

• პირველი ფაზის დროს, რიცხვი 1 გადაადგილდება პირველი პოზიციისაკენ მეზობელ ელემენტებთან ადგილის თანმიმდევრული გაცვლით. 

• მეორე ფაზის დროს, რიცხვი N გადაადგილდება მე-N-ე პოზიციაში.

• მესამე ფაზის დროს რიცხვი 2 გადაადგილდება მე-2-ე პოზიციაში.

• მეოთხე ფაზის დროს, რიცხვი N-1 გადაადგილდება N-1 პოზიციაში.

• და ა.შ.

დაწერეთ პროგრამა, რომელიც გამოთვლის ადგილი გაცვლის რაოდენობებს ამ პროცესის დროს.

შესატანი მონაცემები: პირველ სტრიქონში ერთი მთელი რიცხვი N (1 ≤ N ≤ 100000). მომდევნო N სტრიქონიდან თითოეულში თითო მთელი რიცხვი 1-დან N-მდე (ჩათვლით). მასივში რიცხვი არ მეორდება.

გამოსატანი მონაცემები: თითოეული ფაზისათვის თითო სტრიქონში გამოიტანეთ გაცვლების რაოდენობა.

მაგალითები

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

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

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

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

შესატანი მონაცემები
7
5
4
3
7
1
2
6
                  დაკოპირება

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