მომდევნო ხე

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

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

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

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

წყარო: USACO, 2002/03, DEC, GREEN


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

განვიხილოთ შემდეგი ხე:

 

                               *7

                              /      \

                            /          \

                          /              \

                      *4                3

                       /  \             /     \

                  *1     3       *1       2

                          /  \                /  \

                      *2    1          *1    1

                      /   \

                  *1     1

ვარსკლავებით აღნიშნულია ბესის მიერ ჩამოწერილი წვეროები. ხოლო ხის ამსახველი კოდი შესაბამისად არის (7 4 1 2 1 1 1).

ასე ბესიმ ასახა ფერმერ ჯონის ყველა ხე.  შემდეგ შენიშვნა : 

* ყველა ხეს გააჩნია ფოთლების ერთი და იგივე რაოდენობა;

* ყველა ხეს გააიჩნია განსხვავებული კოდი;

* ბაღში წარმოდგენილია ყველა შესაძლო მკაცრად ბინარული ხე. 

ბეთი შემოქმედებითად მიუდგა საქმეს და მიღებული კოდების სია დაალაგა.  მიჰყევით ბესის და მოცემული ხის კოდის თანახმად მოძებნეთ ის კოდი, რომელიც დალაგებულ მიმდევრობაში მოცემული კოდის უშუალოდ შემდგომია.

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

* სტრიქონი 1: შეიცავს ერთ მთელ L (1<= L <=1000) რიცხვს მე-2 სტრიქონში განთავსებული კოდის სიგრძეს. 

* სტრიქონი  2:  შეიცავს ღარით გამოყოფილ L  ცალ მთელს, რომლების კოდს წარმოადგენენ.

გამომავალი ფაილის ფორმატი:

ერთი სტრიქონი ჰარით გამოყოფილი მთელი რიცხვებით რომლებიც წარმოადგენენ იმ კოდს რომელიც ლექსიკოგრაფიული რიგის მიხედვით მოყვება მოცემულს. თუ შემავალი კოდი სიის მიხედვით უკანასკნელს წარმოადგენს, მაშინ დაბეჭდეთ 0. გახსოვდეთ რომ ხეები ფოთლების ერთი და იგივე რაოდენობისგან შესდგებიან. 

 

 




მაგალითები

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