5. Analýza kombajnových úrodičov

V dedine Kombajnov žije mladý nádejný kombajn Michal Kombajnerle. Kombajnerle obhospodaruje svoje pole, na ktorom rastie množstvo kukurice. Všetka kukurica na jeho poli rastie v jednom dlhom rade. Jedna rastlina kukurice vedľa druhej. Jednotlivé rastliny Kombajnerleho kukurice môžu byť rôzne vysoké.

Pri zbere je dôležité odstrihnúť z rastliny iba klas. Takto ostane v kukurici veľmi málo odpadu. Kombajnerle počas zberu prejde celé pole zľava doprava. Zaujíma ho, ako veľmi bude musieť pohybovať svojim strihačom hore a dole. Na to ešte Kombajnerleho prastarý otec z druhého kolena, Ondrej Kombajnáček, zaviedol prešpekulovanú metriku.

Postupne sa pozrie na každý súvislý úsek poľa kukurice. V úseku sa pozrie, aká vysoká je tam najvyššia a aká vysoká je tam najnižšia rastlina. Rozdiel týchto dvoch výšok prehlási za extremálny extraktor daného úseku. Na konci sčíta všetky extremálne extraktory a výsledok prehlási za supersumarizér daného poľa.

Keďže počítanie supersumarizéru je zdĺhavé, Kombajnerle by tento proces rád automatizoval…

Úloha

Dostanete popis Kombajnerleho poľa kukurice vo forme \(n\) čísiel. Jednotlivé čísla predstavujú výšky jednotlivých rastlín kukurice v poradí, v akom rastú na Kombajnerleho poli.

Definujme extremálny extraktor úseku poľa ako rozdiel maximálnej a minimálnej hodnoty v danom úseku. Ďalej definujme supersumarizér poľa ako súčet extremálnych extraktorov cez všetky neprázdne úseky daného poľa.

Vašou úlohou bude vypočítať supersumarizér Kombajnerleho poľa.

Formát vstupu

Na prvom riadku vstupu sa nachádza celé číslo \(n\) – počet rastlín kukurice na Kombajnerleho poli. Platí \(1 \leq n \leq 10^6\).

Na druhom riadku vstupu je \(n\) medzerou oddelených celých čísiel \(v_1\) až \(v_n\) – výšky rastlín kukurice na Kombajnerleho poli v poradí v akom rastú vedľa seba. Platí \(1 \leq v_i \leq 10^6\).

Je 8 sád vstupov. Pre jednotlivé sady naviac platia nasledovné obmedzenia:

Formát výstupu

Na jedinom riadku výstupu vypíšte jedno číslo – supersumarizér poľa zo vstupu.

Príklady

Input:

3
1 3 2

Output:

5

V tomto prípade má pole 6 neprázdnych úsekov: [1], [3], [2], [1, 3], [3, 2] a [1, 3, 2]. Extremálne extraktory týchto úsekov sú postupne 0, 0, 0, 2, 1 a 2.

Input:

7
2 5 2 2 7 1 8

Output:

107