{-# LANGUAGE BangPatterns, MultiWayIf #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Int
import Data.Foldable
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import Debug.Trace

solve :: Int -> VU.Vector Int -> Int
solve !n !an = dp V.! (n - 1) VU.! (n - 1)
 where
  dp :: V.Vector (VU.Vector Int)
  dp = V.postscanl'
    (\(!dpi) (!i) -> VU.postscanl'
      (\(!dpij) (!j) -> if
        | i > j -> 0
        | even (n - 1 - j + i) -> max (dpi VU.! j + an VU.! i)
                                      (dpij + an VU.! j)
        | otherwise -> min (dpi VU.! j - an VU.! i) (dpij - an VU.! j)
      )
      0
      (VU.fromList [0 .. n - 1])
    )
    (VU.replicate n 0)
    (V.convert $ VU.reverse $ VU.fromList [0 .. n - 1])

main = do
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt = fmap (first fromIntegral . second B.tail) . B.readInt

  n  <- (\(!vec) -> (vec VU.! 0)) . VU.unfoldrN 1 readInt <$> B.getLine
  an <- VU.unfoldrN n readInt <$> B.getLine
  print $ solve n an
