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

-- `binSearch p` searches for an integer `n` s.t. n = min {p k | k \in nat}
binSearch :: (Int -> Bool) -> Int
binSearch pred = if pred 0
  then 0
  else let k = findInterval pred in search (k `div` 2) k
 where
  findInterval pred = head $ dropWhile (not . pred) $ map (2 ^) [0 ..]

  -- (x,y]
  search x y
    | y - x == 1
    = y
    | otherwise
    = let z = (x + y) `div` 2 in if pred z then search x z else search z y

solve :: Int -> VU.Vector Int -> Int
solve !n !an = binSearch canSplitWithin
 where
  sum = VU.sum an

  isWithIn d acc =
    length acc == 4 && let acc' = sort acc in last acc' - head acc' <= d

  canSplitWithin d = isWithIn d $ (\(!x, _, _) -> x) $ fix
    (\(!f) (!acc, !cur, !i) -> if
      | i == VU.length an
      -> (cur : acc, 0, i)
      | cur + an VU.! i < thMin
      -> f (acc, cur + an VU.! i, i + 1)
      | cur > thMax
      -> ([], 0, 0)
      | length acc >= 4
      -> ([], 0, 0)
      | otherwise
      -> let res1 =
               let result@(!acc', _, _) = f ((cur + an VU.! i) : acc, 0, i + 1)
               in  if isWithIn d acc' then Just result else Nothing
             res2 =
               let result@(!acc', _, _) = f (acc, an VU.! i + cur, i + 1)
               in  if isWithIn d acc' then Just result else Nothing
         in  maybe ([], 0, 0) id $ res1 <|> res2
    )
    ([], 0, 0)
   where
    thMin = ceiling (fromIntegral (sum - 3 * d) / 4)
    thMax = floor (fromIntegral (sum + 3 * d) / 4)

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
