local k, n = string.match(io.read(), "(%d+) (%d+)")
k = tonumber(k)
n = tonumber(n)

local a = {}

for x in string.gmatch(io.read(), "(%d+)") do
    table.insert(a, tonumber(x))
end

table.sort(a, function(a, b) return a < b end)
table.insert(a, 1, a[n])
table.insert(a, k + a[2])

local ans = 9999999999

for i = 2, n+1 do
    local t = a[i - 1] - a[i]
    
    if t < 0 then
        t = t + k
    end

    ans = math.min(ans, t)
end

print(ans)