-- ALDS1_1_D Maximum Profit

import Data.Array

main = interact $ (flip (++) "\n") . show . (\(n:xs) -> greatestDiff (take n xs)) . map read . lines

-- post: returns an array, a, of length equal to xs, where
-- a[i] = min {xs[j] : j <= i}
leasts (x:xs) = leasts' (x:xs) x
leasts' [] _ = []
leasts' (x:xs) g = if x < g then x:(leasts' xs x) else g:(leasts' xs g)

-- post: returns an array, g, of length equal to xs, where
-- g[i] = max {xs[j] : j >= i}
greatests :: [Int] -> [Int]
greatests = reverse . aux . reverse
    where aux (x:xs) = greatests' [] (x:xs) x
          greatests' front [] _ = reverse front
          greatests' front (x:xs) l = if x > l then (greatests' (x:front) xs x) else (greatests' (l:front) xs l)

greatestDiff xs = let (l:ls) = leasts xs
                      (_:g:gs) = greatests xs
                      getmax _ [] m = m
                      getmax [] _ m = m
                      getmax (l:ls) (g:gs) m = getmax ls gs (if g - l > m then g - l else m)
                  in  getmax ls gs (g - l)