import Data.List

-- 二分探索をするやつ。単調な条件関数 f と、f ok を満たす ok、f ng を満たさない ng を与えると、f x をギリギリ満たすような x を返す
ibsearch :: (Int -> Bool) -> (Int,Int) -> Int
ibsearch f (ok,ng) = if abs (ok-ng) <= 1 then ok else let mid = (ok + ng) `div` 2 in ibsearch f (if f mid then (mid,ng) else (ok,mid))

-- 悲しさ値の計算関数
f a b = sum $ map abs $ zipWith (-) a [b+1..]

-- b と b+1 の悲しさ値の差分。これは単調。
diff a b = f a (b+1) - f a b

-- 悲しさ値の差分が非負になるような値を求め、その値における悲しさ値を返す。これは悲しさ値の最小値となる。
calc a = let b = ibsearch ((>=0) . diff a) (maximum a, minimum a - length a - 1) in f a b

main = getLine >> getLine >>= print . calc . map read . words
