import qualified Data.ByteString.Char8 as BC
import qualified Data.Heap as H
import Data.Maybe (fromJust)
import Data.List

bias = 10^5

main = do
  n <- readLn :: IO Int
  a <- getIntListBC
  let ra = reverse a
      sumf = sum $ take n a
      suml = sum $ take n ra
      fHalf = foldl (flip H.insert) H.empty $ take n a
      lHalf = foldl (flip H.insert) H.empty $ map ((-) bias) $ take n ra
      first = ((:)sumf) . solveMax fHalf sumf (H.minimum fHalf) $ take n $ drop n a
      latter = ((:)suml) . solveMin lHalf suml (H.minimum lHalf) $ take n $ drop n ra
      ans = zipWith (-) first $ reverse latter
  print $ maximum ans

bsToInt :: BC.ByteString -> Int
bsToInt = fst . fromJust . BC.readInt

getIntListBC :: IO [Int]
getIntListBC = map bsToInt . BC.words <$> BC.getLine

solveMax :: H.Heap Int -> Int -> Int -> [Int] -> [Int]
solveMax _    _   _ []     = []
solveMax heap sum m (a:as) =
  let heap' = if a > m
                then H.insert a $ H.deleteMin heap
                else heap
      sum' = if a > m then sum + a - m
                      else sum
      m' = if a > m then H.minimum heap'
                    else m
  in sum' : (solveMax heap' sum' m' as)

solveMin :: H.Heap Int -> Int -> Int -> [Int] -> [Int]
solveMin _    _   _ []     = []
solveMin heap sum m (a:as) =
  let a' = bias - a
      heap' = if a' > m
                then H.insert a' $ H.deleteMin heap
                else heap
      sum' = if a' > m then sum + a - (bias - m)
                       else sum
      m' = if a' > m then H.minimum heap'
                     else m
  in sum' : (solveMin heap' sum' m' as)
