program answer
  implicit none
  integer(16) :: N, i, ans, a, b, count
  integer(16), allocatable :: P(:), s(:)
  read(*,*) N
  allocate(P(N),S(N))
  do i = 1, N
     read(*,*) P(i)
  end do

  do i = 1, n
     s(p(i))=i
  end do

  count=1
  ans=1
  do i = 1, n-1
     if(s(i)<s(i+1)) then
        count=count+1
     else
        ans=max(ans,count)
        count=1
     end if
  end do

  ans=max(ans,count)

  write(*,*) n-ans

  deallocate(P,S)
  stop
 end program answer