import Data.Char
import Data.List
import qualified Data.ByteString.Char8 as B
main=print.solve.unfoldr(B.readInt.B.dropWhile isSpace)=<<B.getContents
solve=fst.foldl' f(0,0).tail
f(s,p)a=(s+b-a,b)where b=max p a