K,N=io.read("*n","*n")
A={}
for i=1,N do
A[i]={i,io.read"*n"}
end
table.sort(A,function(a,b)return a[2]<b[2]end)
B={}
for i=1,N-1 do
B[i]={i,A[i+1][2]-A[i][2]}
end
B[N]={N,K+A[1][2]-A[N][2]}
local max=B[1]
for i=2,N do
	if(B[i][2]>max[2])then max=B[i] end
end
print(K-max[2])