import java.util.Scanner


import scala.io.StdIn._

object Main extends App {

  val Array(k,n) = readLine().split(" ").map(_.toInt)

  val A = readLine().split(" ").map(_.toInt)

  def solve() = {
    val maxDis = (0 until n).foldLeft(0) { (acc, i) =>
      val dis = if(i != n-1) A(i+1) - A(i) else k - A(i) + A(0)
      Math.max(acc, dis)
    }
    k - maxDis
  }

  println(solve())

}

