def main():

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

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

    ans = float('inf')

    for i in range(N):

        if A[i] > A[i-1]:

            tmp = (K + A[i-1]) - A[i]

        else:

            tmp = A[i-1] - A[i]

        ans = min(ans, tmp)



    for i in range(N):

        if i == N - 1:

            tmp = A[i] - A[0]

        else:

            tmp = K - (A[i+1] - A[i])

        ans = min(ans, tmp)



    print(ans)







if __name__ == "__main__":

    main()
def main():

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

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

    B = [0] * (2 * N)



    for i in range(2*N):

        if i < N:

            B[i] = A[i]

        else:

            B[i] = K + A[i - N]



    l = 0

    for i in range(N):

        tmp = B[i+1] - B[i]

        l = max(l, tmp)



    ans = K - l

    print(ans)







if __name__ == "__main__":

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


if __name__ == "__main__":
    main()

def main():
    K, N = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = [0] * (2 * N)
    for i in range(2 * N):
        if i < N:
            B[i] = A[i]
        else:
            B[i] = K + A[i - N]
    l = 0
    for i in range(N):
        tmp = B[i + 1] - B[i]
        l = max(l, tmp)
    ans = K - l
    print(ans)


if __name__ == "__main__":
    main()

-    ans = float("inf") +    B = [0] * (2 * N) +    for i in range(2 * N): +        if i < N: +            B[i] = A[i] +        else: +            B[i] = K + A[i - N] +    l = 0 -        if A[i] > A[i - 1]: -            tmp = (K + A[i - 1]) - A[i] -        else: -            tmp = A[i - 1] - A[i] -        ans = min(ans, tmp) -    for i in range(N): -        if i == N - 1: -            tmp = A[i] - A[0] -        else: -            tmp = K - (A[i + 1] - A[i]) -        ans = min(ans, tmp) +        tmp = B[i + 1] - B[i] +        l = max(l, tmp) +    ans = K - l