data Monotony = Dec | Inc | Nmn deriving (Eq, Show)

monotony :: [Int] -> Monotony
monotony [a,b,c] =
    if a<b  then if b<c then Inc
                        else Nmn
            else if b>=c then Dec
                        else Nmn

kanashimi b xs = aux b 0 1 xs
    where
        aux _ ac _ []     = ac
        aux b ac i (x:xs) = aux b (ac+abs(x-b-i)) (i+1) xs

range n xs = [kanashimi b xs | b <- [n-1..n+1]]

monoAt n xs = monotony $ range n xs

main = do
    n <- getLine
    xs <- ((fmap read . words) <$> getLine) :: IO [Int]
    let b = b_ini xs
    let l = b-50
    let u = b+50
    print $ solveR ((l, monoAt l xs),(u, monoAt u xs)) xs 1000

b_ini :: [Int] -> Int
b_ini xs = ceiling (ave xs) - (div (length xs) 2)

solve :: Int -> [Int] -> Int
solve n xs = do
    let [a,b,c] = range n xs
    case monotony [a,b,c] of
        Inc -> solve (n-1) xs
        Dec -> solve (n+1) xs
        Nmn -> b

solveR :: ((Int,Monotony),(Int,Monotony)) -> [Int] -> Int -> Int
solveR ((l,Dec), (u,Dec)) xs p = do
    let nr = u+p
    solveR ((u,Dec),(nr,monoAt nr xs)) xs p
solveR ((l,Inc), (u,Inc)) xs p = do
    let nl = u-p
    solveR ((nl,monoAt nl xs),(l,Inc)) xs p
solveR ((l,Dec), (u,Inc)) xs p
    | u-l < 100 = solve (ceiling $ ave [u,l]) xs
    | otherwise = do
        let nr = u-div (u-l) 2+1
        solveR ((l,Dec),(nr,monoAt nr xs)) xs (div (u-l) 4)


ave :: [Int] -> Double
ave xs = fromIntegral (sum xs) / fromIntegral (length xs)
