main = print . abs . solve1 . map read . drop 1 . words =<< getContents

solve1 :: [Integer] -> Integer
solve1 xs =
    let diffs = zipWith (-) (drop 1 xs) xs
    in  solve2 diffs

maxVal = 1000000000

solve2 :: [Integer] -> Integer
solve2 [] = maxVal
solve2 (x:[]) = x
solve2 xs =
    let l = take (length xs `div` 2) xs
        r = drop (length xs `div` 2) xs
        ls = solve2 l
        rs = solve2 r
        ms = abs $ (minHeads $ reverse l) + (minHeads r)
    in  minimum [ls, rs, ms]

minHeads :: [Integer] -> Integer
minHeads xs = let (_, res) = foldr (\x (t, s) -> (t+x, min (abs (t+x)) (abs s))) (0, head xs) (tail xs) in res
