{-# LANGUAGE FlexibleContexts #-}

import Control.Monad
import Control.Applicative
import Data.List
import Data.Array
import Data.Array.IO
import Data.Maybe
import qualified Data.ByteString.Char8 as BS


readIntBS = fst . fromJust . BS.readInt

main = do
  n <- readLn :: IO Int
  ps <- map readIntBS . BS.lines <$> BS.getContents :: IO [Int]

  arr <- newArray (1,n) 0 :: IO (IOUArray Int Int)
  asc <- newArray (1,n) 0 :: IO (IOUArray Int Int)
  dsc <- newArray (1,n) 0 :: IO (IOUArray Int Int)

  forM_ (zip [1..] ps) $ \(i,p) -> do
    writeArray arr p i

  let
    aux1 i a = do
      when (i <= n) $ do
        x <- readArray arr i
        y <- readArray arr (i-1)
        if y < x then
          writeArray asc i a >> aux1 (i+1) a
          else
          writeArray asc i i >> aux1 (i+1) i

    aux2 i a = do
      when (i >= 1) $ do
        x <- readArray arr i
        y <- readArray arr (i+1)
        if y > x then
          writeArray dsc i a >> aux2 (i-1) a
          else
          writeArray dsc i i >> aux2 (i-1) i
          

  writeArray asc 1 1
  aux1 2 1

  writeArray dsc n n
  aux2 (n-1) n

  print =<< (n -) . maximum <$> (zipWith (\x y -> y-x+1) <$> getElems asc <*> getElems dsc)
