import Data.Bool
import Data.List
import Data.Ord

main = interact $ show . sol . fmap (fmap read . words) . lines

sol :: [[Int]] -> Int
sol [[n],as] = f n as

f n as
  | n == 0    = sum l - sum r
  | n == 1    = maximum [as!!1-as!!2, as!!0-as!!2, as!!0-as!!1]
  | odd n     = f (n-1) $ bool (l++r') (l'++r) (x<y)
  | otherwise = f (n-2) $ maximumBy (comparing (f 0)) [l''++r,l'++r',l++r'']
  where
  m = (length as+1) `div` 2
  l = take m as
  r = drop (length as-m) as
  (x,l') = g l
  (y,r') = h r
  (_,l'') = g l'
  (_,r'') = h r'

g xs = let x = minimum xs in (x,xs\\[x])
h xs = let x = maximum xs in (x,xs\\[x])