Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: darzelis.in

Rezultatų failas: darzelis.out

Jei norite pateikti savo sprendimą - prisijunkite.

Vaikų darželis

Darželyje vaikai yra suskirstomi grupėmis. Mokytoja surikiuoja vaikus į eilę ir kiekvienam vaikui priskiria charizmos reikšmę. Kiekvienas vaikas turi patekti į lygiai vieną grupę. Kiekviena grupė yra ne tuščias iš eilės einančių vaikų intervalas. Grupės draugiškumo reikšme pavadinsime maksimalų dviejų toje pačioje grupėje esančių vaikų charizmos skirtumą. (Jei grupę sudaro 1 vaikas, draugiškumo indeksas lygus 0).

Mokytoja nori padalinti vaikus į grupes taip, kad grupių draugiškumo reikšmių suma būtų maksimali.

Jūsų užduotis rasti šią maksimalią reikšmę.

Pradiniai duomenys

Pirmoje eilutėje duotas vienas skaičius n (1\\leqn\\leq10^6) - vaikų skaičius.

Antroje eilutėje duota n skaičių a_i (-10^9\\leqa_i\\leq10^9) - vaikų charizmos reikšmės.

Rezultatai

Išveskite vieną skaičių - maksimalią draugiškumo reikšmių sumą.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5
1 2 3 1 2
 
3