Dělení amuletu

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.



Obrázek 1. Příklad amuletů jejichž tvar odpovídá binární haldě. Vrcholy reprezentují korálky, hrany reprezentují řemínky. Čísla uvnitř vrcholů jsou ceny jednotlivých korálků. Řetízky, které si bojovníci odeberou, jsou vyznačeny růžovou barvou. Jsou navíc očíslovány v pořadí, v jakém budou odebrány. a) Budou odebrány celkem tři řetízky, s cenami postupně 13, 5 a 1. a) Budou odebrány celkem čtyři řetízky, s cenami postupně 24, 10, 8 a 2.

Ú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.

Výstup

Výstup sestává z jednoho řádku, který obsahuje celočíselnou hodnotu R, jež odpovídá celkovému počtu řetízků, které si bojovníci z amuletu odeberou.

Příklad 1

Vstup
7
2 2 1 1 1 6 6
Výstup
3
Data a řešení Příkladu 1 jsou znázorněny na Obrázku 1a).

Příklad 2

Vstup
11
2 3 3 4 4 8 8 2 4 4 2
Výstup
4
Data a řešení Příkladu 2 jsou znázorněny na Obrázku 1b).

Příklad 3

Vstup
12
2 1 5 3 5 1 1 1 4 4 5 4
Výstup
4

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.
Veřejná data