{-# LANGUAGE RecordWildCards #-}

import           Data.Function (on)
import           Data.List     (groupBy)
import           Data.Tree     (Tree (Node, rootLabel, subForest))

import Data.Monoid

main :: IO ()
main = interact $ show . f . getNumbers

getNumbers :: String -> [Int]
getNumbers input =
  let
    first : second : _ = lines input
    n = read first
  in
    take n . map read . words $ second

f :: [Height] -> Int
f = getSum . (Sum . stripe <> Sum . allPattern) . toTree

type Width = Int
type Height = Int
type RectangleTree = Tree (Width, Height)

toTree :: [Height] -> RectangleTree
toTree [] = error "empty list"
toTree [n] = Node { rootLabel = (1, n), subForest = [] }
toTree ns = Node { rootLabel = (width, minHeight), subForest = map toTree (scrape ns) }
  where
    minHeight = minimum ns
    width = length ns

    scrape :: [Height] -> [[Height]]
    scrape = filter ((0 /=) . head) . groupBy ((==) `on` (0 ==)) . map (subtract minHeight)

-- test1 :: Bool
-- test1 = f (getNumbers input) == 12800
--   where
--     input = "9\
-- \2 3 5 4 1 2 4 2 1"

stripe :: RectangleTree -> Int
stripe Node { rootLabel = (_, h), .. } = 2 ^ h * product (map stripe subForest)

notStripe :: RectangleTree -> Int
notStripe Node { rootLabel = (w, _), subForest = [] } = 2 ^ w - 2
notStripe Node { rootLabel = (w, h), .. } =
  2 ^ (w - childrenTotalWidth subForest) * product (map stripe subForest)
  where
    childrenTotalWidth = sum . map (fst . rootLabel)

allPattern :: RectangleTree -> Int
allPattern t@Node { rootLabel = (w, _), subForest = [] } = stripe t + 2 ^ w - 2
allPattern Node { rootLabel = (w, h), .. } =
  2 ^ (w - childrenTotalWidth subForest) * product (map (\t -> allPattern t) subForest) +
  (2 ^ h - 2) * product (map stripe subForest)
  where
    childrenTotalWidth = sum . map (fst . rootLabel)
