2sec

Най-хубавият имот на селянина Йон представлява редица от ябълкови дървета, номерирани с числата от 1 до N.
От известно време Йон почувствал, че силите му намаляват и решил да даде част от дърветата на своите двама сина.
По-малкият от синовете създавал доста неприятности на баща си и затова Йон решил следното:

- всеки от синовете ще получи дървета, разположени на последователни позиции в редицата от ябълки;
- броят на ябълките за всеки от синовете може да бъде различен, но всеки син ще получи поне по едно дърво;
- малкият син ще получи дървета с по-малки номера от номерата на дърветата, предназначени за големия син;
- разликата между приходите на големия син от получените дървета и приходите на малкия син трябва да бъде максимална.
Приходите, които носи едно отделно дърво са пресметнати от Йон по специална формула, която той е усъвършенствал през годините.

Задача
Напишете програма, която намира търсената максимална разлика.

Вход

Първият ред на входния файл 2sec.in съдържа цяло положително число N, представляващо броя на ябълковите дървета. Вторият ред съдържа N цели числа, разделени с интервал, като i-тото число показва каква е печалбата от i-тото дърво.

Изход

Изходният файл 2sec.out трябва да съдържа единствен ред, на който е записана максималната разлика, която може да бъде получена според изискванията на Йон.

Ограничения

1 < N < 1001001
-128 < печалбата от всяко отделно дърво < 128

Пример

2sec.in	2sec.out	Обяснение
10 8 -5 1 -3 7 -3 2 8 -3 1	21	8 -5 1 -3 7 -3 2 8 -3 1 Червените дървета са предназначени за малкия син, а сините – за големия син. Разликата е: 7-3+2+8-(-5+1-3)=14-(-7)=21

Ограничение за време: 0.5 секунди на тест

Fechete Dan Ionut
University of Bucharest, Mathematics & IT Department
f.dan.ionut@gmail.com

Превод на български: Стоян Капралов