BST

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

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

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

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

წყარო: COCI, 2008/09, #3


ძებნის ორობითი ხე წარმოადგენს სტრუქტურას, რომლის თითოეულ წვეროს გააჩნია რაიმე რიცხვითი მნიშვნელობა და გარდა ამისა, ჰყავს არაუმეტეს ორი შვილი. თითოეული წვეროსთვის მარცხენა ქვეხეში შემავალი ელემენტები ნაკლებია ამ წვეროს მნიშვნელობაზე, ხოლო მარჯვენა ქვეხეში შემავალი ელემენტები - მეტია. თქვენ გეძლევათ 1-დან N-მდე (ჩათვლით) რიცხვების სიმრავლე, სადაც ყველა რიცხვი განსხვავებულია, და უნდა ააგოთ ძებნის ორობითი ხე რიცხვების თანმიმდევრული ჩასმით. პირველი რიცხვი იქნება ხის სათავე. სხვა სიტყვებით გაუშვით ქვემოთ ნაჩვენები insert(X, root) ყოველი რიცხვისთვის:

insert( number X, node N )

    increase the counter C by 1

    if X is less than the number in node N

           if N has no left child

                 create a new node with the number X and set it to be the left child of node N

                                          else

                    insert(X, left child of node N)

    else (X is greater than the number in node N)

                    if N has no right child

                          create a new node with the number X and set it to be the right child of node N

                                                 else

                          insert(X, right child of node N)

დაწერეთ პროგრამა, რომელიც გამოითვლის C მთვლელის მნიშვნელობას ყოველი რიცხვისთვის. მთვლელის თავდაპირველი მნიშვნელობა არის 0.

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

გამოსატანი მონაცემები: N მთელი რიცხვი (თითო სტრიქონში - თითო) - C მთვლელის მნიშვნელობა შესაბამისი რიცხვის ხეში ჩასმისას.




მაგალითები

შესატანი მონაცემები
4 1 2 3 4 დაკოპირება
გამოსატანი მონაცემები
0 1 3 6 დაკოპირება
შესატანი მონაცემები
5 3 2 4 1 5 დაკოპირება
გამოსატანი მონაცემები
0 1 2 4 6 დაკოპირება
შესატანი მონაცემები
8 3 5 1 6 8 7 2 4 დაკოპირება
გამოსატანი მონაცემები
0 1 2 4 7 11 13 15 დაკოპირება