Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: 2018_stovykla_vyr_seka.in

Rezultatų failas: 2018_stovykla_vyr_seka.out

Jei norite pateikti savo sprendimą - prisijunkite.

Seka

Jums bus duota skaičų seka a_1,a_2,\\ldots,a_n. Su šia seka galima atlikti vieną vienintelę operaciją apjungti(i). Po apjungimo aperacijos ties pozija i, sekos elementai a_i ir a_{i+1} pakeičiami nauju elementu max(a_i,a_{i+1}) -- tokio apjungimo kaina max(a_i,a_{i+1}).

Po n-1 apjungimo operacijos, seka yra sumažinama iki vieno elemento.

Užduotis

Rasti mažiausia sekos sumažinimo iki vieno elemento kainą.

Pradiniai duomenys

Pirmoje eilutėje įrašyti skaičius 1\\leqn\\leq10^6 nurodantis sekos ilgį. Likusiose n eilučių pateikta po viena sekos elementą 0\\leqa_i\\leq10^9.

Rezultatai

Jums reikės išvesti vieną skaičių -- mažiausią sekos sumažinimo iki vieno elemento kainą.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3
1
2
3
 
5