import Data.List

data S = Up | Down | Other deriving (Eq)

countBandT :: Ord a => S -> [a] -> ([a],[a])
countBandT _ [] = ([],[])
countBandT status [a] | status == Up   = ([], [a])
                      | status == Down = ([], []) 
                      | otherwise = ([],[a])
countBandT Other (a:b:ls) | a < b = ((fst $ countBandT Up (b:ls)), snd $ countBandT Up (b:ls))
                          | a > b = ((fst $ countBandT Down (b:ls)), (a : (snd $ countBandT Down (b:ls))))
                          | otherwise = countBandT Other (b:ls)
countBandT status (a:b:ls) | status == Down && a < b = ((a : (fst $ countBandT Up (b:ls))), snd $ countBandT Up (b:ls))
                           | status == Up && a > b   = ((fst $ countBandT Down (b:ls)), (a : (snd $ countBandT Down (b:ls))))
                           | otherwise = countBandT status (b:ls)

water :: Int -> Int -> ([Int],[Int]) -> Int
water _ _ ([],[]) = 0
water count n (bs,ts) = n + (water (count+1) (n+(fst $ numOf count bs)-(fst $ numOf count ts)) (snd $ numOf count bs, snd $ numOf count ts))

numOf0 :: Int -> Int -> [Int] -> (Int,[Int])
numOf0 c _ [] = (c,[])
numOf0 c n (x:xs) | n == x    = numOf0 (c+1) n xs
                  | otherwise = (c,(x:xs))

numOf = numOf0 0

main :: IO ()
main = do
  n <- read <$> getLine :: IO Int
  hs <- map read.words <$> getLine :: IO [Int]
  let bt = countBandT Other hs
  putStrLn $ show $ (water 0 1 (sort $ fst bt, sort $ snd bt)) - 1
