import Data.Maybe
import Data.List
import qualified Data.ByteString.Char8 as C

parseInt :: C.ByteString -> Int
parseInt = fst . fromJust . C.readInt

data State = State
  { stOrd :: Ordering,
    stHas :: Bool,
    stOpt :: Integer
  } deriving (Show)

instance Eq State where
  (==) (State o1 h1 _) (State o2 h2 _) = o1 == o2 && h1 == h2

stPlus :: State -> State -> Integer
stPlus (State _ _ v1) (State _ _ v2) = v1 + v2

isOk :: State -> Bool
isOk (State EQ _ _) = True
isOk _ = False

reduceStates :: [State] -> Integer
reduceStates states = maximum $ map stOpt $ filter isOk states

isMatch :: State -> State -> Bool
isMatch (State o1 _ _) (State o2 _ _) =
  case (o1, o2) of
    (EQ, EQ) -> True
    (LT, GT) -> True
    (GT, LT) -> True
    _ -> False

match :: [State] -> [State] -> Integer
match [] [] = 0
match [] ss = match ss []
match ss [] = reduceStates ss
match ss1 ss2 = maximum $ [stPlus s t | s <- ss1, t <- ss2, isMatch s t]

f :: [Integer] -> [[State]]
f [] = []
f [x] = [[State LT False 0, State GT True x]]
f (x : xs) =
  foldl' merge [] (ss' >>= trans) : ss' : sss'
  where
  (ss' : sss') = f xs
  trans (State ord has opt) =
    if has
      then case ord of
        LT -> []
        GT -> [State EQ False opt]
        EQ -> [State LT False opt]
      else case ord of
        LT -> [State EQ True (opt + x)]
        GT -> [State EQ False opt]
        EQ -> [State GT True (opt + x), State LT False opt]
  merge states state =
    case partition (==state) states of
      ([], _) -> state : states
      ([State ord' has' opt'], states') -> State ord' has' (max opt' $ stOpt state) : states'
      _ -> error ""

main :: IO ()
main = do
  n <- parseInt <$> C.getLine
  as <- map (fromIntegral . parseInt) . C.words <$> C.getLine
  let s = f as
      t = reverse $ f $ reverse as
      ans = if n `mod` 2 == 0
        then reduceStates $ head s
        else maximum $ zipWith match (tail s ++ [[]]) ([] : init t)
  putStrLn $ show ans
