Bounce Game
TopCoder Custom Round
Time Limit: 0.4s, Memory Limit: 64MiB
Ели играе на следната компютърна игра. N плочки са наредени в редичка от ляво надясно. Върху всяка плочка има написано число Ai. В началото на играта, играчът избира начална плочка и посока (ляво или дясно). След това героят на играча е поставен на въпросната плочка в избраната посока. Това е единствената интеракция на играча с играта – от тук нататък тя се развива по начина, описан в следващия параграф.

В началото точките на играча са нула. Играта се развива в ходове. Всеки ход се формира от следните три стъпки:

  1. Героят на играча прочита числото на плочката, в която се намира и го добавя към точките на играча.
  2. Ако числото на плочката е нечетно, героят добавя към него 1, презаписва го върху плочката, и сменя посоката си. Например, ако героят е гледал надясно и числото на текущата плочката е било 17, той ще добави 17 към точките на играча, ще замени числото на плочката с 18, и ще се обърне наляво.
  3. Героят прави стъпка напред и застава върху следващата плочка в посоката, в която гледа. Ако стъпката напред изкара героя извън дъската, играта свършва.

Сега Ели ви е помолила да намерите най-големия възможен резултат, който може да се получи при оптимално поставяне на героя и началната му посока.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броя плочки, които има в дъската на играта. На следващия ред ще бъдат зададени N цели числа A1, A2, ..., AN – числата, записани на всяка от плочките (зададени от най-лявата към най-дясната).
Изход
На стандартния изход изведете едно цяло число – максималния резултат, който може да бъде получен.
Ограничения
  • 1 ≤ N ≤ 5,000
  • 1 ≤ Ai ≤ 1,000,000,000
Примерен Вход Примерен Изход
4 42 13 17 17 139
11 90 77 103 4 17 38 33 21 55 91 100 1695
В първия пример оптималния резултат може да бъде постигнат поставяйки героя на втората клетка (индексирано от нула) – тоест лявата 17-ка. Героят трябва да гледа надясно. Записаните от играча точки са: 17 + 13 + 18 + 17 + 18 + 14 + 42 = 139.
Мрън!