program main
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: n,i,maxdiff=0
    integer(int32), allocatable:: p(:),pre(:)
    logical,allocatable:: see(:)

    read*, n
    allocate(p(n))
    allocate(pre(n), source=[(i,i=1,n)])
    allocate(see(0:n), source=.false.)
    read*, (p(i), i=1,n)
    
    do i=1,n
        see(p(i)) = .true.
        if (.not. see(p(i)-1)) cycle
        pre(p(i)) = pre(p(i)-1)
        maxdiff = max(maxdiff,p(i)-pre(p(i))+1)
    end do

    print'(i0)', n-maxdiff
end program main