{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE Unsafe #-}
{-# LANGUAGE RecordWildCards #-}

import Data.Bits
import Data.List
import qualified Data.ByteString.Char8 as BS
import qualified Data.Vector.Unboxed as VU
import Control.Monad
import Control.Monad.ST
import Control.Applicative


main :: IO ()
main = do
  n <- read <$> getLine
  ls <- VU.unfoldrN n (BS.readInt . BS.dropWhile (==' ')) <$> BS.getLine
  print $ binSearch 0 n ls

binSearch :: Int -> Int -> VU.Vector Int -> Int
binSearch ng ok ls | ok - ng <= 1 = ok
binSearch ng ok ls =
  if isPossibleWith mid ls then
    binSearch ng mid ls
  else
    binSearch mid ok ls
  where
    mid = (ng + ok) `shiftR` 1


isPossibleWith :: Int -> VU.Vector Int -> Bool
isPossibleWith 1 ls = VU.and $ VU.zipWith (<) ls (VU.tail ls)
isPossibleWith numChars ls
  = VU.foldr loop (\_ _ -> True) ls 0 Nil
  where
    loop !reqLen cont wordLen charList
      | reqLen > wordLen = cont reqLen charList
      | otherwise = loop1 (cont reqLen)
                    (cutOff charList reqLen) (reqLen - 1)
    loop1 _ !xs ind | ind < 0 = False
    loop1 cont xs@(Snoc xs' i e) ind = case compare i ind of
      LT -> cont $! Snoc xs ind 1
      EQ | e < numChars - 1 -> cont $! Snoc xs' i (e+1)
         | otherwise        -> loop1 cont xs' (ind-1)
    loop1 cont Nil ind = cont $! Snoc Nil ind 1

data List = Nil | Snoc !List {-# UNPACK #-} !Int {-# UNPACK #-} !Int
 deriving Show


cutOff :: List -> Int -> List
cutOff (Snoc xs i e) till | till <= i = cutOff xs till
cutOff xs !till = xs
