# ABC160_C

k,n=list(map(int,input().split()))

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

# mid=(a[0]+a[-1])/2

d=[]

for i in range(n-1):

    d.append(a[i+1]-a[i])

# d.append(k-a[-1])

# d=[k-a[-1]]+d



# print(d)

ans=10**10

d=[k-a[-1]+a[0]]+d

d+=[k-a[-1]+a[0]]

# print(d)

for i in range(1,n):

    t=min(k-d[i-1],k-d[i+1])

    ans=min(t,ans)

print(ans)

k,n=list(map(int,input().split()))

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

d=[]

d.append(k-a[-1]+a[0])

for i in range(1,n):

  d.append(a[i]-a[i-1])

ans=10**18

for di in d:

  t=k-di

  ans=min(ans,t)

print(ans)
# ABC160_C
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
# mid=(a[0]+a[-1])/2
d = []
for i in range(n - 1):
    d.append(a[i + 1] - a[i])
# d.append(k-a[-1])
# d=[k-a[-1]]+d
# print(d)
ans = 10**10
d = [k - a[-1] + a[0]] + d
d += [k - a[-1] + a[0]]
# print(d)
for i in range(1, n):
    t = min(k - d[i - 1], k - d[i + 1])
    ans = min(t, ans)
print(ans)

k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
d = []
d.append(k - a[-1] + a[0])
for i in range(1, n):
    d.append(a[i] - a[i - 1])
ans = 10**18
for di in d:
    t = k - di
    ans = min(ans, t)
print(ans)

-# ABC160_C -# mid=(a[0]+a[-1])/2 -for i in range(n - 1): -    d.append(a[i + 1] - a[i]) -# d.append(k-a[-1]) -# d=[k-a[-1]]+d -# print(d) -ans = 10**10 -d = [k - a[-1] + a[0]] + d -d += [k - a[-1] + a[0]] -# print(d) +d.append(k - a[-1] + a[0]) -    t = min(k - d[i - 1], k - d[i + 1]) -    ans = min(t, ans) +    d.append(a[i] - a[i - 1]) +ans = 10**18 +for di in d: +    t = k - di +    ans = min(ans, t)