Optimal ikili axtarış ağacı

$S=\{e_1,e_2,...,e_n\}$ çoxluğunu nəzərdən keçirək, burada $n$ fərqli element var və $e_1<e_2<...<e_n$ şərtini ödəyir. İndi $S$ elementlərindən ibarət olan binar axtarış ağacını düşünək. Elementə nə qədər tez-tez müraciət olunursa, o, kökə bir o qədər yaxın yerləşməlidir.

Ağacda $S$-dən olan $e_i$ elementinə girişin dəyəri $cost(e_i)$ adlanır və bu, kök elementinə birləşdirən yoldakı kənarların sayına bərabərdir. $S$-dən olan elementlərə müraciət tezliklərini $(f(e_1),f(e_2),...,f(e_n))$ nəzərə alaraq, ağacın ümumi dəyərini aşağıdakı kimi müəyyən edək:

Ən az dəyərə malik ağac, $S$-dən olan elementlərin axtarışı üçün ən yaxşı hesab olunur. Buna görə də, bu ağac Optimal Binar Axtarış Ağacı adlanır.

Giriş verilənləri

Bir neçə testdən ibarətdir, hər biri ayrıca sətirdə yerləşir. Sətirdəki ilk ədəd $n(1\le n\le 250)$ $S$ çoxluğunun ölçüsünü göstərir. Növbəti $n$ qeyri-mənfi tam ədədlər $S$-dən olan elementlərin müraciət tezliklərini təsvir edir: $f(e_1),f(e_2),...,f(e_n)(0\le f(e_i)\le 100)$.

Çıxış verilənləri

Hər bir test üçün ayrıca sətirdə Optimal Binar Axtarış Ağacının dəyərini çıxarın.

Nümunələr