{-# LANGUAGE BangPatterns #-}

-- This code was written after reading the editorial.

import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe
import Data.List
import Debug.Trace
import System.Random
import Control.Monad

solve :: Int -> [Int] -> [Int]
solve n as | n `mod` 2 == 0 = reverse $ sort [sum_even, sum_odd]
           | otherwise = [sum_odd + diff, sum_even - diff]
  where
    sum_all = sum as
    sum_even = f_sum_even as
    sum_odd = sum_all - sum_even
    diff = calc_diff (max 0 (sum_even-sum_odd)) (sum_even + 1) as

f_sum_even as = sub 0 as
  where
    sub !acc []       = acc
    sub !acc [a]      = acc + a
    sub !acc (a:_:as) = sub (acc+a) as

calc_diff dmin dmax as
  | dmax == dmin + 1 = dmin
  | try dmid as = calc_diff dmid dmax as
  | otherwise = calc_diff dmin dmid as
  where
    dmid = (dmax + dmin) `div` 2

try goal [a] = goal <= a
try goal (w0:b0:as@(w1:as'))
  | w0 >= goal && w0 <= b0 = try goal as
  | otherwise              = try goal (w1 + (w0-b0) : as')

bsReadInts :: B.ByteString -> [Int]
bsReadInts = map (fst . fromJust . B.readInt) . B.words

main = do
  cont <- B.getContents
  let (n:as) = bsReadInts cont
      ans= solve n as
  putStrLn $ unwords $ map show ans
