import sys





def input():

    return sys.stdin.readline().strip()





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

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

Diff = []

for i in range(N - 1):

    Diff.append(A[i + 1] - A[i])

Diff.append(K - A[-1] + A[0])

print((K - max(Diff)))

import sys





def input():

    return sys.stdin.readline().strip()





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

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

A.append(K + A[0])

Diff = [y - x for x, y in zip(A, A[1:])]

answer = K - max(Diff)

print(answer)

import sys


def input():
    return sys.stdin.readline().strip()


K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
Diff = []
for i in range(N - 1):
    Diff.append(A[i + 1] - A[i])
Diff.append(K - A[-1] + A[0])
print((K - max(Diff)))

import sys


def input():
    return sys.stdin.readline().strip()


K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
A.append(K + A[0])
Diff = [y - x for x, y in zip(A, A[1:])]
answer = K - max(Diff)
print(answer)

-Diff = [] -for i in range(N - 1): -    Diff.append(A[i + 1] - A[i]) -Diff.append(K - A[-1] + A[0]) -print((K - max(Diff))) +A.append(K + A[0]) +Diff = [y - x for x, y in zip(A, A[1:])] +answer = K - max(Diff) +print(answer)