ტურბო სორტირება

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: COCI, 2007/08, #2


მირკომ უნდა დაალაგოს მასივი, რომელიც შეიცავს 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 დაკოპირება