k,n,*l=list(map(int,open(0).read().split()));print((min((l[i-1]-l[i])%k for i in range(n))))
k,n,*l=list(map(int,open(0).read().split()))

print((k-max((l[i]-l[i-1])%k for i in range(n))))
k, n, *l = list(map(int, open(0).read().split()))
print((min((l[i - 1] - l[i]) % k for i in range(n))))

k, n, *l = list(map(int, open(0).read().split()))
print((k - max((l[i] - l[i - 1]) % k for i in range(n))))

-print((min((l[i - 1] - l[i]) % k for i in range(n)))) +print((k - max((l[i] - l[i - 1]) % k for i in range(n))))