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

3
1
2
3

5