# -*- coding: utf-8 -*-





def calc(k, kiten, a):

    koho1 = abs(kiten -a)

    koho2 = kiten + k - a

    koho3 = a + k - kiten



    return min(koho1, koho2, koho3)





def main():

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

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



    max_kkn = a_list[0] + k - a_list[-1]

    for i in range(n - 1):

        max_kkn = max(max_kkn, a_list[i + 1] - a_list[i])



    print((k - max_kkn))





if __name__ == '__main__':

    main()

# -*- coding: utf-8 -*-





def calc(k, kiten, a):

    koho1 = abs(kiten -a)

    koho2 = kiten + k - a

    koho3 = a + k - kiten



    return min(koho1, koho2, koho3)





def main():

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

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



    max_kkn = a_list[0] + k - a_list[-1]

    for a, b in zip(a_list, a_list[1:]):

        max_kkn = max(max_kkn, b - a)



    print((k - max_kkn))





if __name__ == '__main__':

    main()

# -*- coding: utf-8 -*-
def calc(k, kiten, a):
    koho1 = abs(kiten - a)
    koho2 = kiten + k - a
    koho3 = a + k - kiten
    return min(koho1, koho2, koho3)


def main():
    k, n = list(map(int, input().split()))
    a_list = list(map(int, input().split()))
    max_kkn = a_list[0] + k - a_list[-1]
    for i in range(n - 1):
        max_kkn = max(max_kkn, a_list[i + 1] - a_list[i])
    print((k - max_kkn))


if __name__ == "__main__":
    main()

# -*- coding: utf-8 -*-
def calc(k, kiten, a):
    koho1 = abs(kiten - a)
    koho2 = kiten + k - a
    koho3 = a + k - kiten
    return min(koho1, koho2, koho3)


def main():
    k, n = list(map(int, input().split()))
    a_list = list(map(int, input().split()))
    max_kkn = a_list[0] + k - a_list[-1]
    for a, b in zip(a_list, a_list[1:]):
        max_kkn = max(max_kkn, b - a)
    print((k - max_kkn))


if __name__ == "__main__":
    main()

-    for i in range(n - 1): -        max_kkn = max(max_kkn, a_list[i + 1] - a_list[i]) +    for a, b in zip(a_list, a_list[1:]): +        max_kkn = max(max_kkn, b - a)