Dělení amuletu
Zadání
Indiáni kmene Lakota se účastní posvátného rituálu, při kterém si mladí bojovníci dělí amulet "Padající voda". Tento amulet sestává z korálků a řemínků, které vytvářejí stromovou strukturu shodující se tvarem s perfektně vyváženým binárním stromem, ve kterém poslední hladina, zaplněná listy z leva do prava, nemusí být kompletní. Mladí bojovníci přistupují k amuletu jednolivě, v pořadí podle jejich věku. Každý si odřízne jeden řetízek korálků a stává se jeho majitelem. Řetízkem zde nazýváme každou souvislou část tvořenou jedním či více korálky, kde každý korálek je spojen řemínkem s nejvýše dvěma sousedy. Korálky mají různou cenu a bojovníci jsou natolik bystří, že maximalizují hodnotu svého řetízku danou součtem cen jeho korálků.
Amulet je během celého rituálu položený tak, jak je zachyceno na Obrázku 1. Při odříznutí řetízků nedochází z rituálních důvodů k přemístění korálků, které nejsou odebrány. Díky odřezávání řemínků se amulet může postupně rozpadat na oddělené části. V případě, že existuje více způsobů, jak odříznout řetízek nejvyšší ceny, volí každý bojovník z více možností ten řetízek, ve kterém je korálek s nejmenší hloubkou ve výchozí podobě amuletu co nejvíce vlevo (jeho číslo v pořadí inorder v amuletu je minimální). Není-li volba řetízku stále jednoznačná, je preferován ten řetízek, ve kterém je absolutní hodnota rozdílu inorder pořadí jeho koncových korálků co nejvyšší (pro jednokorálkové řetízky je tento rozdíl definován jako 0).
Během rituálu je celý amulet rozebrán. Může se tak stát, že na některé z nejmladších bojovníků žádné korálky nezbydou.
Úloha
Je dána struktura amuletu a cena jeho jednotlivých korálků. Určete, jaké řetízky si budou bojovníci z amuletu postupně odebírat.
Vstup
První vstupní řádek obsahuje celé kladné číslo N, které udává počet korálků amuletu.
Druhý vstupní řádek obsahuje N celých kladných čísel oddělených mezerami. Čísla reprezentují cenu jednotlivých korálků pokud korálky uspořádáme po hladinách stromu, na každé hladině zleva doprava. Jinými slovy, řádek čísel představuje reprezentaci perfektně vyváženého binárního stromu, plněného po hladinách zleva doprava, v poli.
Platí N ≤ 1.2 × 105. Hodnota každého korálku není větší než 2000.