program main
  
  
  implicit none
  integer :: k,n
  integer, allocatable :: a(:), b(:)
  integer :: i, tmp, ans ,tmp1
  
  read(*,*) k,n
  allocate( a(n) )
  allocate( b(n) )
  read(*,*) b 

  call quicksort1( b, 1, n)

  a(1) = b(1) 
  do i = 2, n 
    a(i) = b(i) - b(i-1)
  end do

  tmp = k - b(n) + b(1)
  
  call quicksort1( a, 1, n)

  if ( a(n) > tmp ) then
    print*, k - a(n)
  else
    print*, k - tmp
  end if
  
end program main

recursive subroutine quicksort1(a, first, last)
  implicit none
  integer(4),intent(inout)::a(*)
  integer,intent(in)::first,last
  !
  ! Original
  ! https://gist.github.com/t-nissie/479f0f16966925fa29ea
  !
  integer(4)::x,t
  integer::i,j

  x = a((first+last)/2)
  i = first
  j = last
  do
     do while (a(i) < x)
        i=i+1
     end do
     do while (x < a(j))
        j=j-1
     end do
     if (i >= j) exit
     t = a(i)
     a(i) = a(j)
     a(j) = t
     i=i+1
     j=j-1
  end do
  if (first < i-1) call quicksort1(a, first, i-1)
  if (j+1 < last)  call quicksort1(a, j+1, last)

  return
end subroutine quicksort1
