scuze

După ce Abi a filmat ultimul lui său clip într-un liceu din capitală, el s-a întrebat:

Dându-se un șir de numere $v[1], v[2], \ldots, v[N]$, definim costul unei subsecvențe $v[i..j]$ unde $1 \leq i \leq j \leq N$ ca find suma valorilor de pe pozițiile impare ($i$, $i + 2$, etc.) minus suma valorilor de pe pozițiile pare ($i + 1$, $i + 3$, etc.). Să se calculeze valoarea absolută minimă a costului unei subsecvențe.

Formal, Abi vrea să afle:

Date de intrare

Pe prima linie se va afla $N$. Pe a doua linie se vor afla $v[1], v[2], \dots v[N]$, separate prin spații.

Date de ieșire

Pe prima linie se va afișa valoarea absolută minimă a costului unei subsecvențe a lui $v$, calculată conform lui Abi.

Restricții

• $1 \leq N \leq 100 \ 000$
• $-10^9 \leq v[i] \leq 10^9$ pentru $1 \leq i \leq N$

Exemplu 1

stdin

5
-43 37 63 43 -32

stdout

12

Explicație

Pentru primul exemplu, haideți să calculăm valoarea absolută a costului câtorva subsecvențe:

• $v[1..2] \rightarrow \ | -43 - 37 | = 80$
• $v[2..5] \rightarrow \ | 37 - 63 + 43 - (-32) | = 49$
• $v[3..5] \rightarrow \ | 63 - 43 + (-32) | = 12$

Minimul este $12$, corespunzând subsecvenței $v[3..5]$.

Exemplu 2

stdin

10
-47 24 10 -48 -17 81 72 35 -16 10  

stdout

3

Explicație

Pentru al doilea exemplu, obținem valoarea $3$ dacă alegem subsecvența $v[3..8]$ deoarece $| 10 - (-48) + (-17) - 81 + 72 - 35 | = | -3 | = 3$.