Žeņaskalni

Alpīnisti Ferdinands un Izabella ir nolēmuši izstaigāt slavenos Žeņaskalnus. Kartē Žeņaskalnu nogāzes izskatās kā nogriežņi, kuru galapunkti atrodas punktos ar veselām koordinātām un ir vērsti $45^\circ$ vai $135^\circ$ pret abscisu asi, turklāt katri divi secīgi nogriežņi ir savstarpēji perpendikulāri. Tas ļauj aprakstīt Žeņaskalnus kā veselu nenegatīvu skaitļu virkni, kas sākas ar $0$, kam seko lauzuma punktu (virsotņu un ieleju) augstumu ordinātu virkne. Skaitļu virkne beidzas ar $0$.

Piemēram, 1. zīmējumā parādīto kalnu apraksts ir $0$, $5$, $2$, $8$, $0$.

Lai būtu interesantāk, Ferdinands un Izabella ir nolēmuši kāpšanu kalnos sākt katrs no sava kalnu grēdas gala un visu laiku pārvietoties tā, lai katrā brīdī atrastos vienādā augstumā virs sākuma līmeņa (abscisu ass kartē). Pēc tam, kad Ferdinands un Izabella ir satikušies, viņi aprēķina kopējo viena alpīnista veikto pārvietojumu līdz satikšanās brīdim (abiem tas ir vienāds). Ja ceļojuma laikā alpīnists secīgi ir atradies punktos ar augstumu virs sākuma līmeņa $a_1$, $a_2$, $\dots$, $a_m$, tad pārvietojumu aprēķina kā augstumu starpību moduļu summu: $|a_1-a_2|+|a_2-a_3|+\dots+|a_{m-1}-a_m|$. Protams, ka alpīnisti vēlas satikties pēc iespējas agrāk - tā, lai pārvietojums būtu mazākais iespējamais.

Aplūkotajā piemērā sākumā Ferdinands atrodas punktā $A(0;0)$, bet Izabella - $G(22;0)$. Tad viņi abi var doties augšup, visu laiku atrodoties vienādā augstumā, līdz Ferdinands sasniedz $B(5;5)$, bet Izabella - $E(17;5)$. Izabella nevar turpināt ceļu augšup, jo Ferdinands nevarēs atrasties tādā pat augstumā. Toties viņi abi var vienlaicīgi doties lejup - Ferdinands uz $C(8;2)$, bet Izabella uz $F(20;2)$. Tagad abi alpīnisti var doties augšup un satikties punktā $D(14;8)$. Katra alpīnista veiktais pārvietojums ir $|0-5|+|5-2|+|2-8|=14$.

Uzrakstiet datorprogrammu, kas dotam kalnu grēdas aprakstam nosaka viena alpīnista mazāko iespējamo pārvietojumu no kāpšanas sākuma līdz satikšanās brīdim!

Pirmajā rindā dots kalnus aprakstošo nogriežņu skaits - naturāls skaitlis $N (N \leq 5000)$. Otrajā rindā dots $N+1$ vesels nenegatīvs skaitlis. Pirmais un pēdējais no šiem skaitļiem ir $0$. Katram $i(1 < i \leq N)$ $i$-tais skaitlis rindā ir $i$-tā nogriežņa sākumpunkta (kas vienlaikus ir $(i-1)$-ā nogriežņa beigu punkts) ordinātas vērtība. Zināms, ka punktu ordinātu vērtības nepārsniedz $10^9$.

Starp katriem diviem blakus skaitļiem ievaddatos ir tukšumzīme.

Izvaddatu vienīgajā rindā jābūt naturālam skaitlim - viena alpīnista veiktajam mazākajam iespējamajam pārvietojumam no sākuma brīža, kad tas atrodas kalnu pakājē, līdz satikšanās ar otru alpīnistu brīdim. Tiek garantēts, ka vienmēr eksistē tāds ceļojums, ka abi alpīnisti satiksies.