import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Ord

main :: IO ()
main = getLine >> readLine >>= print . solve

solve :: [Int] -> Int
solve hs
    | all (== 0) hs = 0
    | otherwise = edit0 . dropWhile (== 0) . map head $ group hs
    where
        edit0 (x : y : zs) = count0 $ x : edit x (y : zs)
        edit0 [x] = x

        edit p (x : y : zs)
            | (p < x && x > y) || (p > x && x < y) = x : edit x (y : zs)
            | otherwise = edit x $ y : zs
        edit _ xs = xs

        count0 (x : y : zs)
            | x > y = x + count (y : zs)
            | otherwise = x + count (x : y : zs)
        
        count (x : y : zs) = y - x + count zs
        count _ = 0

readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine