K, N, *A = list(map(int, open(0).read().split()))



diff = A[0] + K - A[-1]

for i in range(1, N):

    diff = max(diff, A[i] - A[i - 1])

print((K - diff))



from os import readlink





K, N = list(map(int, input().split()))

X = list(map(int, input().split()))



ans = K - (X[0] + K - X[-1])

for i in range(1, N):

    ans = min(ans, K - (X[i] - X[i - 1]))

print(ans)

K, N, *A = list(map(int, open(0).read().split()))
diff = A[0] + K - A[-1]
for i in range(1, N):
    diff = max(diff, A[i] - A[i - 1])
print((K - diff))

from os import readlink

K, N = list(map(int, input().split()))
X = list(map(int, input().split()))
ans = K - (X[0] + K - X[-1])
for i in range(1, N):
    ans = min(ans, K - (X[i] - X[i - 1]))
print(ans)

-K, N, *A = list(map(int, open(0).read().split())) -diff = A[0] + K - A[-1] +from os import readlink + +K, N = list(map(int, input().split())) +X = list(map(int, input().split())) +ans = K - (X[0] + K - X[-1]) -    diff = max(diff, A[i] - A[i - 1]) -print((K - diff)) +    ans = min(ans, K - (X[i] - X[i - 1])) +print(ans)