magnify

Seka

Pradinių duomenų failas:
seka.in  
Rezultatų failas:
seka.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Duota seka \(a_{1}\) , …, \(a_{n}\). Šią seką galima keisti operacija reduce(i), kuri elementus \(a_{i}\) ir \(a_{i+1}\) pakeičia vienu elementu max(\(a_{i}\), \(a_{i+1}\)) (t.y. didesniuoju iš dviejų), ir taip gaunama nauja, trumpesnė seka. Šios operacijos kaina yra max(\(a_{i}\), \(a_{i+1}\)).

Atlikus n reduce operacijų gaunama vienetinio ilgio seka. Parašykite programą, kuri suskaičiuotų, kokia yra mažiausia galima sekos sutrumpinimo iki vienetinės sekos kaina.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas sveikas skaičius n – sekos ilgis (1 ≤ n ≤ 1000000). Kitose n eilučių įrašyta po vieną sveiką skaičių \(a_{i}\) – tai sekos elementai (0 ≤ \(a_{i}\)  ≤ 1000000000).

Rezultatai

Į rezultatų failą jūsų programa turi išvesti vienintelį skaičių – mažiausią galimą sekos sutrumpinimo iki vienetinės sekos kainą.

Pavyzdys

Pradiniai duomenys Rezultatai
3
1
2
3
5
© Bronė Narkevičienė