Dzelzceļa līnijā ir N stacijas, kas sanumurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Ir zināms attālums kilometros starp katrām divām blakusesošām stacijām. Pagaidām dzelzceļa līnijā ir tikai viens sliežu ceļš, bet ir nolemts sākt būvēt dublējošos sliežu ceļus tā, lai no katras stacijas vismaz uz vienu no kaimiņu stacijām būtu divi paralēli sliežu ceļi un lai dublējošo sliežu ceļu kopgarums būtu pēc iespējas mazāks.

Piemēram, dzelzceļa līnijā var būt piecas stacijas un attālums starp blakusesošām stacijām tāds, kā redzams zīmējumā:

Tad dublējošie sliežu ceļi jābūvē starp 1. un 2., 3. un 4., 4. un 5. staciju:

Šajā gadījumā dublējošo sliežu ceļu kopgarums ir 17 kilometri.

Uzrakstiet programmu, kas dotam staciju skaitam un attālumam starp blakusesošām stacijām aprēķina īsāko iespējamo dublējošo sliežu ceļu kopgarumu!

Teksta datnes celi.dat pirmajā rindā dots naturāls skaitlis N (1 < N ≤ 1 000 000). Katrā no nākamajām N-1 datnes rindām dots viens naturāls skaitlis, kura vērtība nepārsniedz 1000, - attālums starp divām blakusesošām stacijām. Katram i (2 ≤ i ≤ N) attālums starp (i-1)-o un i-to staciju ir dots datnes i-tajā rindā.

Teksta datnes celi.rez vienīgajā rindā jāizvada viens naturāls skaitlis - īsākā iespējamā dublējošā sliežu ceļa kopgarums.

5
7
13
4
6

17

4
7
1
13

20

 
Uzdevums izmantots Latvijas 22. informātikas olimpiādē 2009. gadā.