import java.util.Scanner

fun main(args: Array<String>){
    val scn = Scanner(System.`in`)
    val v = scn.nextLine().split(" ")
    val K = v[0].toInt()
    val N = v[1].toInt()
    val Ai =  scn.nextLine().split(" ").map { i -> i.toInt() }

    val sortAi = Ai.sorted()

    var max = 0
    var maxInd = 0
    (0 until Ai.size).forEach {i ->
        var tmp = 0
        if(i==0){
            tmp = K - sortAi[Ai.size-1] + sortAi[0]
        }else{
            tmp = sortAi[i]-sortAi[i-1]
        }
        if(tmp >= max){
            max = tmp
            maxInd = i
        }
    }

    var i = maxInd
    val end = if(maxInd==0) Ai.size-1 else maxInd -1
    var result = 0

    do{
        if(i==Ai.size-1){
            result += K - sortAi[Ai.size-1] + sortAi[0]
            i=0
        }else{
            result += sortAi[i+1] - sortAi[i]
            i++
        }
    }while (i!=end)


    print(result)
}