def c_traveling_salesman_around_lake():

    K, N = [int(i) for i in input().split()]

    A = [int(i) for i in input().split()]



    pos = [-(K - a) for a in A] + A[:]

    diff = [abs(pos[i + 1] - pos[i]) for i in range(len(pos) - 1)]

    ans = sum(diff[:N - 1])

    tmp = ans



    left, right = 0, N - 1

    while right != len(diff):

        tmp -= diff[left]

        tmp += diff[right]

        ans = min(ans, tmp)

        left += 1

        right += 1

    return ans



print((c_traveling_salesman_around_lake()))
def c_traveling_salesman_around_lake():

    K, N = [int(i) for i in input().split()]

    A = [int(i) for i in input().split()]  # ソート済

    A.append(A[0] + K)  # N 番の家と 1 番の家の間の距離も調べたい



    return K - max(A[i + 1] - A[i] for i in range(N))



print((c_traveling_salesman_around_lake()))
def c_traveling_salesman_around_lake():
    K, N = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    pos = [-(K - a) for a in A] + A[:]
    diff = [abs(pos[i + 1] - pos[i]) for i in range(len(pos) - 1)]
    ans = sum(diff[: N - 1])
    tmp = ans
    left, right = 0, N - 1
    while right != len(diff):
        tmp -= diff[left]
        tmp += diff[right]
        ans = min(ans, tmp)
        left += 1
        right += 1
    return ans


print((c_traveling_salesman_around_lake()))

def c_traveling_salesman_around_lake():
    K, N = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]  # ソート済
    A.append(A[0] + K)  # N 番の家と 1 番の家の間の距離も調べたい
    return K - max(A[i + 1] - A[i] for i in range(N))


print((c_traveling_salesman_around_lake()))

-    A = [int(i) for i in input().split()] -    pos = [-(K - a) for a in A] + A[:] -    diff = [abs(pos[i + 1] - pos[i]) for i in range(len(pos) - 1)] -    ans = sum(diff[: N - 1]) -    tmp = ans -    left, right = 0, N - 1 -    while right != len(diff): -        tmp -= diff[left] -        tmp += diff[right] -        ans = min(ans, tmp) -        left += 1 -        right += 1 -    return ans +    A = [int(i) for i in input().split()]  # ソート済 +    A.append(A[0] + K)  # N 番の家と 1 番の家の間の距離も調べたい +    return K - max(A[i + 1] - A[i] for i in range(N))