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

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



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

ans = A[-1] - A[0]

for i in range(1, N):

    dist = K - A[i] + A[i - 1]

    if dist < ans:

        ans = dist



print(ans)

import sys





def input():

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





def main():

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

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



    ans = [K - A[i] + A[i - 1] for i in range(1, N)]

    print((min(min(ans), A[-1] - A[0])))





main()

K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
diff = A[0] + K - A[-1]
ans = A[-1] - A[0]
for i in range(1, N):
    dist = K - A[i] + A[i - 1]
    if dist < ans:
        ans = dist
print(ans)

import sys


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


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


main()

-K, N = list(map(int, input().split())) -A = list(map(int, input().split())) -diff = A[0] + K - A[-1] -ans = A[-1] - A[0] -for i in range(1, N): -    dist = K - A[i] + A[i - 1] -    if dist < ans: -        ans = dist -print(ans) +import sys + + +def input(): +    return sys.stdin.readline().strip() + + +def main(): +    K, N = list(map(int, input().split())) +    A = list(map(int, input().split())) +    ans = [K - A[i] + A[i - 1] for i in range(1, N)] +    print((min(min(ans), A[-1] - A[0]))) + + +main()