Ели се запали по програмирането и скоро написа първата си игра. Е, не е 3D shooter, или 2D стратегия... Тя е 1D!

Играта представлява човече, което се движи наляво и надясно по хоризонтална отсечка, разграфена в N полета. От дадено поле човечето може да се придвижи само в съседното ляво или дясно (където има такива) полета. В началото човечето се намира в най-лявото поле. То прави ход (определен брой стъпки надясно); после втори ход (определен брой стъпки наляво); после прави трети ход (пак надясно) и т.н., докато реши да се откаже (което може да направи по всяко време - включително още в самото начало, стъпвайки само на началното поле). С времето човечето се изморява: ако на предходния ход е направило S стъпки в дадена посока, на следващия ход то прави най-много S-1 в обратната.

Във всяко поле има записано цяло число A_i (положително, отрицателно, или нула). Всеки път, когато човечето стъпи в дадено поле, към точките му се прибавя числото в него. Крайният резултат на играча са текущите му точки, в момента, в който е решил да се отакже.

Ели се пита колко най-много точки може да се спечелят в дадено ниво на играта при оптимална игра? На първия ред на стандартния вход ще бъде зададено едно цяло число N - броят полета върху хоризонталната отсечка на даденото ниво. На втория ред ще бъдат зададени N на брой цели числа A_i – числата, записани във всяко от полетата. На стандартния изход изведете едно цяло число – максималния брой точки, които могат да бъдат постигнати за даденото ниво.

• 1 ≤ N ≤ 500
• -10,000 ≤ A_i ≤ 10,000

Примерен Вход	Примерен Изход
5 -1 -5 17 -13 42	60
3 -42 0 -13	-42
22 -97 75 99 81 7 -85 77 -94 31 61 -52 -99 -96 0 -36 25 10 -17 -56 -20 79 0	817