There is a circular pond with a perimeter of K meters, and N houses around them.
The i-th house is built at a distance of A_i meters from the northmost point of the pond, measured clockwise around the pond.
When traveling between these houses, you can only go around the pond.
Find the minimum distance that needs to be traveled when you start at one of the houses and visit all the N houses.

-----Constraints-----
 - 2 \leq K \leq 10^6
 - 2 \leq N \leq 2 \times 10^5
 - 0 \leq A_1 < ... < A_N < K
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
K N
A_1 A_2 ... A_N

-----Output-----
Print the minimum distance that needs to be traveled when you start at one of the houses and visit all the N houses.

-----Sample Input-----
20 3
5 10 15

-----Sample Output-----
10

If you start at the 1-st house and go to the 2-nd and 3-rd houses in this order, the total distance traveled will be 10.
[{"code": "k, n = map(int, input().split())\npoints = list(map(int, input().split()))\n\ndist = []\nfor i in range(n):\n    if i != n-1:\n        distance = points[i+1] - points[i]\n    else:\n        distance = points[0]+k - points[i]\n    dist.append(distance)\n\nmax = dist[0]\nfor j in range(1, len(dist), 1):\n    if max < dist[j]:\n        max = dist[j]\ndist.remove(max)\n\nans = 0\nfor k in dist:\n    ans += k\nprint(ans)", "passed": true, "time": 0.29, "memory": 14272.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na = list(map(int, input().split()))\n\nd = []\nfor i in range(n - 1):\n    d.append(a[i + 1] - a[i])\nd.append(k - a[n - 1] + a[0])\nd.sort()\nprint(sum(d[:-1]))", "passed": true, "time": 0.15, "memory": 14088.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA_l = sorted(map(int, input().split()))\nd_l = [K+A_l[0]-A_l[N-1]]\nfor i in range(1, N):\n    d_l.append(A_l[i]-A_l[i-1])\nprint(K-max(d_l))", "passed": true, "time": 0.15, "memory": 14060.0, "status": "done"}, {"code": "k,n = map(int,input().split())\na = list(map(int,input().split()))\ntemp = 0\nfor i in range(n-1):\n    temp = max(temp,a[i+1]-a[i])\ntemp = max(temp,k-a[n-1]+a[0])\nprint(k-temp)", "passed": true, "time": 0.14, "memory": 14096.0, "status": "done"}, {"code": "# import math\n# import statistics\n# import itertools\n# a=int(input())\n# b,c=int(input()),int(input())\n# c=[]\n# for i in a:\n#     c.append(int(i))\nA,B= map(int,input().split())\nf = list(map(int,input().split()))\n# g = [input().split for _ in range(a)]\n# h = []\n# for i in range(a):\n#     h.append(list(map(int,input().split())))\n# a = [[0] for _ in range(H)]#nizigen\nkyori=[]\nfor i in range(len(f)-1):\n    an=f[i+1]-f[i]\n    kyori.append(an)\n    \nan2=A-f[-1]+f[0]\nans=max(max(kyori),an2)\nprint(A-ans)", "passed": true, "time": 0.15, "memory": 14064.0, "status": "done"}, {"code": "def i_input(): return int(input())\n\n\ndef i_map(): return map(int, input().split())\n\n\ndef i_list(): return list(map(int, input().split()))\n\n\ndef i_row(N): return [int(input()) for _ in range(N)]\n\n\ndef i_row_list(N): return [list(map(int, input().split())) for _ in range(N)]\n\n\nk, n = i_map()\naa = i_list()\ndif=[]\nfor i in range(n):\n    if i==n-1:\n        dif.append(k-aa[-1]+aa[0])\n    else:\n        dif.append(aa[i+1]-aa[i])\nprint(k-max(dif))", "passed": true, "time": 0.23, "memory": 14132.0, "status": "done"}, {"code": "K,N=map(int,input().split())\nA=list(map(int,input().split()))\nB=[0]*N\nfor i in range(N-1):\n  B[i]=A[i+1]-A[i]\nB[N-1]=K-A[N-1]+A[0]\nprint(K-max(B))", "passed": true, "time": 0.14, "memory": 14224.0, "status": "done"}, {"code": "k, n = list(map(int, input().split()))\na = list(map(int, input().split()))\nmx = a[0] + k - a[n - 1]\nfor i in range(n - 1):\n    mx = max(mx, a[i + 1] - a[i])\nprint((k - mx))\n", "passed": true, "time": 0.14, "memory": 14264.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\nA_list = list(map(int, input().split()))\nA_list.append(K + A_list[0])\n\ndif_list = [0] * N\n\nfor i in range(N):\n    dif_list[i] = A_list[i + 1] - A_list[i]\n\nprint(K - max(dif_list))", "passed": true, "time": 0.14, "memory": 14168.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na = list(map(int,input().split()))\ntmp = 0\nansl = [] \nfor i in range(n-1):\n    tmp = a[i+1] - a[i]\n    ansl.append(tmp)\ntmp = k - a[-1] + a[0]\nansl.append(tmp)\nprint(k -max(ansl))", "passed": true, "time": 0.15, "memory": 14204.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na = list(map(int, input().split()))\n\nm = 0\nfor i in range(n-1):\n  if a[i+1]-a[i]>m:\n    m = a[i+1]-a[i]\nif k-a[n-1]+a[0]>m:\n  m = k-a[n-1]+a[0]\nprint(k-m)", "passed": true, "time": 0.14, "memory": 14316.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA = list(map(int, input().split()))\n\nmax_d = 0\n\nfor a in range(1, N):\n    d = A[a] - A[a-1]\n    if d > max_d:\n        max_d = d\nlast_d = K - A[-1] + A[0]\nif last_d > max_d:\n    max_d = last_d\nprint(K - max_d)", "passed": true, "time": 0.27, "memory": 14096.0, "status": "done"}, {"code": "k,n = map(int, input().split())\na = list(map(int, input().split()))\n\nans = 10000000\nfor i in range(n-1):\n    ans = min(k-(a[i+1]-a[i]), ans)\nans = min(ans,a[n-1]-a[0])\nprint(ans)", "passed": true, "time": 0.14, "memory": 14048.0, "status": "done"}, {"code": "k,n = map(int,input().split())\nL = list(map(int,input().split()))\nL.append(k+L[0])\nm = 0\n\nfor i in range(n):\n  m = max(m, L[i+1]-L[i])\n\nprint(k-m)", "passed": true, "time": 0.14, "memory": 14284.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\nA = list(map(int, input().split()))\n\na = 0\nif A[0] == 0:\n    a = K - A[N - 1]\nelse:\n    a = min(A[N - 1] - A[0], K - A[N - 1] + A[0])\n\n\nfor i in range(N - 1):\n    b = A[i + 1] - A[i]\n    a = max(a, b)\nans = K - a\nprint(ans)", "passed": true, "time": 0.14, "memory": 14060.0, "status": "done"}, {"code": "import sys\nimport math\nfrom collections import defaultdict, deque, Counter\nfrom copy import deepcopy\nfrom bisect import bisect, bisect_right, bisect_left\nfrom heapq import heapify, heappop, heappush\n    \ninput = sys.stdin.readline\ndef RD(): return input().rstrip()\ndef F(): return float(input().rstrip())\ndef I(): return int(input().rstrip())\ndef MI(): return map(int, input().split())\ndef MF(): return map(float,input().split())\ndef LI(): return list(map(int, input().split()))\ndef TI(): return tuple(map(int, input().split()))\ndef LF(): return list(map(float,input().split()))\ndef Init(H, W, num): return [[num for i in range(W)] for j in range(H)]\n    \n    \ndef main():\n    K , N = MI()\n    L = LI()\n    res = L[-1] - L[0]\n    max_num = L[-1]\n    for i in range(1, N):\n        temp = L[i]\n        past = L[i-1]\n        past += K - temp\n        res = min(res, past)\n        \n    print(res)\ndef __starting_point():\n    main()\n__starting_point()", "passed": true, "time": 0.14, "memory": 14228.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nAlst = list(map(int, input().split()))\nzero = Alst[0] + K\nM = 0\nnow = Alst[0]\nfor i in Alst:\n    dis = i - now\n    if dis > M:\n        M = dis\n    now = i\n\nlast = zero - now\nif last > M:\n    M = last\n\nprint(K - M)", "passed": true, "time": 0.14, "memory": 14112.0, "status": "done"}, {"code": "k,n = list(map(int,input().split()))\na = list(map(int,input().split()))\n\nroute = []\nfor i in range(n-1):\n    move = a[i+1] - a[i]\n    route.append(move)\n\nroute.append(k-a[-1]+a[0])\n\nprint((sum(route) - max(route)))\n", "passed": true, "time": 0.14, "memory": 14352.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA = list(map(int, input().split()))\nd = [K+A[0]-A[-1]]+[b-a for a, b in zip(A, A[1:])]\nprint(K-max(d))", "passed": true, "time": 0.14, "memory": 14348.0, "status": "done"}, {"code": "k,n = list(map(int,input().split()))\na = list(map(int,input().split()))\n\nb = []\nfor i in range(n-1):\n    b.append(a[i+1]-a[i])\n\nb.append(k-a[-1]+a[0])\n\nprint((sum(b)-max(b)))\n", "passed": true, "time": 0.14, "memory": 14208.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na_list = list(map(int, input().split()))\nlongest = 0\n\nfor i in range(n-1):\n        distance = a_list[i+1] - a_list[i]\n        longest = max(longest, distance)\n\nprint(k-max(longest, k-a_list[n-1]+a_list[0]))", "passed": true, "time": 0.14, "memory": 14144.0, "status": "done"}, {"code": "k,n=map(int,input().split())\nl=list(map(int,input().split()))\nl.sort()\nans=k-l[n-1]+l[0]\nfor i in range(n-1):\n    if l[i+1]-l[i]>=ans:\n        ans=l[i+1]-l[i]\nprint(k-ans)", "passed": true, "time": 0.14, "memory": 14340.0, "status": "done"}, {"code": "# coding=utf-8\n\ndef __starting_point():\n    K, N = map(int, input().split())\n    li = list(map(int, input().split()))\n    li.append(K+li[0])\n\n    l = 0\n    for i in range(N):\n        l = max(l, abs(li[i] - li[i+1]))\n\n    print(K-l)\n__starting_point()", "passed": true, "time": 0.14, "memory": 14208.0, "status": "done"}, {"code": "k,n=map(int,input().split())\nA=list(map(int,input().split()))\na=A\nfor i in range(n):\n  a.append(k+A[i])\nd=[0]*n\nfor i in range(n):\n  d[i]=a[n-1+i]-a[i]\nprint(min(d))", "passed": true, "time": 0.14, "memory": 14100.0, "status": "done"}, {"code": "k, n =map(int,input().split())\na = list(map(int,input().split()))\nlongest = k - a[-1] + a [0]\nfor i in range(len(a)-1):\n    longest = max(longest,a[i+1]-a[i])\nprint(k-longest)", "passed": true, "time": 0.23, "memory": 14308.0, "status": "done"}, {"code": "K,N = list(map(int,input().split()))\ndis = list(map(int,input().split()))\ndif = []\nfor i in range(N-1):\n  dif.append(int(dis[i+1]-dis[i]))\n  \ndif.append(int(K-dis[N-1]+dis[0]))\nprint((K-max(dif)))\n\n", "passed": true, "time": 0.14, "memory": 14328.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\nA = list(map(int, input().split()))\nB = []\n\nfor j in range(N-1):\n    B.append(A[j+1]-A[j])\n\nC = A[0]+K-A[N-1]\nB.append(C)\nB.sort()\nprint((K-B[N-1]))\n", "passed": true, "time": 0.14, "memory": 14112.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na_list = list(map(int, input().split()))\n\nlongest = 0\nfor i in range(n):\n    # if i==0:\n    #     continue\n    if i==n-1:\n        longest = max(longest, k-a_list[i]+a_list[0])\n    else:\n        distance = a_list[i+1] - a_list[i]\n        longest = max(longest, distance)\n\nprint(k-longest)", "passed": true, "time": 0.15, "memory": 14116.0, "status": "done"}, {"code": "k, n = map(int, input().split())\n\na = list(map(int, input().split()))\n\na.append(a[0] + k)\n\nm = 0\n\nfor i in range(n):\n    m = max(m, a[i + 1] - a[i])\n\nprint(k - m)", "passed": true, "time": 0.14, "memory": 14284.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA = list(map(int, input().split()))\n\nd = []\nfor i in range(N-1):\n    d.append(A[i+1] - A[i])\nd.append(A[0] + K - A[N-1])\n\nmax_d = max(d)\n\nprint(K - max_d)", "passed": true, "time": 0.14, "memory": 14284.0, "status": "done"}, {"code": "def main():\n    k, n = map(int, input().split())\n    a = [int(v) for v in input().split()]\n    distances = []\n    for i in range(1, len(a)):\n        distances.append((a[i]-a[i-1]))\n    distances.append((k+a[0]) - a[-1])\n    maximum = max(distances)\n    return k - maximum\n\ndef __starting_point():\n    print(main())\n__starting_point()", "passed": true, "time": 0.15, "memory": 14328.0, "status": "done"}, {"code": "k, n = list(map(int, input().split()))\na = list(map(int, input().split()))\n\nb = []\nfor i in range(n - 1):\n    b.append(a[i + 1] - a[i])\n\nb.append(k - a[-1] + a[0])\n\nprint((sum(b) - max(b)))\n", "passed": true, "time": 0.14, "memory": 14280.0, "status": "done"}, {"code": "#ABC160\nK,N=map(int,input().split())\nA =list(map(int,input().split()))\na=[K-(A[N-1]-A[0])]\nfor i in range(1,N):\n    a.append(abs(A[i]-A[i-1]))\nprint(K-max(a))", "passed": true, "time": 0.25, "memory": 14364.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\nAs = list(map(int, input().split()))\n\nAs += [As[0] + K]\n\nmaxDiff = 0\nfor i in range(N):\n    d = As[i+1]-As[i]\n    if d > maxDiff:\n        maxDiff = d\n\nprint((K-maxDiff))\n", "passed": true, "time": 0.15, "memory": 14296.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na = list(map(int, input().split()))\nroot = []\nans = 0\n\nfor i in range(0, n-1):\n    x = a[i+1] - a[i]\n    root.append(x)\n\ny = a[0] + k - a[n-1]\nroot.append(y)\n\nfor i in root:\n    ans += i\n\nans -= max(root)\nprint(ans)    ", "passed": true, "time": 0.15, "memory": 14104.0, "status": "done"}, {"code": "k, n = map(int,input().split())\na = list(map(int,input().split()))\n\nda =[-1] * n\nda[n-1] = k - a[n-1] + a[0]\nfor i in range(n-1):\n    da[i] = a[i+1] - a[i]\n    \nprint(sum(da)-max(da))", "passed": true, "time": 0.14, "memory": 14212.0, "status": "done"}, {"code": "K,N = map(int,input().split())\nA = [int(i) for i in input().split()]\nL = []\nans = 0\nfor i in range(N):\n    if(i == N-1):\n        L.append(K-A[N-1]+A[0])\n        break\n    L.append(A[i+1]-A[i])\nfor i in range(N):\n    ans += L[i]\nans -= max(L)\nprint(ans)", "passed": true, "time": 0.14, "memory": 14268.0, "status": "done"}, {"code": "try:\n    K, N = map(int,input().split())\n    A = list(map(int, input().split()))\n\n    li = []\n    for i in range(N - 1):\n        li.append(A[i + 1] - A[i]) \n\n    li.append(abs(A[0] + (K - A[-1])))\n    print(sum(li) - max(li))\nexcept:\n    pass", "passed": true, "time": 0.15, "memory": 14344.0, "status": "done"}, {"code": "k, n = map(int, input().split())\nalst = list(map(int, input().split()))\nalst.append(alst[0] + k)\nminus = 0\nfor i in range(n):\n  minus = max(minus, alst[i + 1] - alst[i])\nprint(k - minus)", "passed": true, "time": 0.3, "memory": 14324.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\n\nA = list(map(int, input().split()))\n\nB = []\n\nfor i in range(len(A)-1):\n    B.append(A[i+1]-A[i])\n\nB.append(A[0] - A[N-1] + K)\n\nb_max       = max(B)\nb_max_index = B.index(max(B))\n\n\nB.remove(b_max)\nprint((sum(B)))\n", "passed": true, "time": 0.14, "memory": 14196.0, "status": "done"}, {"code": "import math\nimport decimal\ndef i_input(): return int(input())\n\n\ndef i_map(): return map(int, input().split())\n\n\ndef i_list(): return list(map(int, input().split()))\n\n\ndef i_row(N): return [int(input()) for _ in range(N)]\n\n\ndef i_row_list(N): return [list(map(int, input().split())) for _ in range(N)]\n\nk,n= i_map()\naa=i_list()\ndis=[]\nfor i in range(n):\n    if i == 0:\n        dis.append(k-aa[-1]+aa[0])\n    else:\n        dis.append(aa[i]-aa[i-1])\nprint(k-max(dis))", "passed": true, "time": 0.16, "memory": 14216.0, "status": "done"}, {"code": "import sys\n\nsys.setrecursionlimit(10 ** 8)\nini = lambda: int(sys.stdin.readline())\ninl = lambda: [int(x) for x in sys.stdin.readline().split()]\nins = lambda: sys.stdin.readline().rstrip()\ndebug = lambda *a, **kw: print(\"\\033[33m\", *a, \"\\033[0m\", **dict(file=sys.stderr, **kw))\n\n\ndef solve():\n    k, n = inl()\n    A = inl()\n    dmax = A[0] + (k - A[-1])\n    for i in range(1, n):\n        dmax = max(dmax, A[i] - A[i - 1])\n    return k - dmax\n\n\nprint(solve())\n", "passed": true, "time": 0.14, "memory": 14084.0, "status": "done"}, {"code": "k, n = map(int ,input().split())\na = list(map(int,input().split()))\n\na.append(k+a[0])\n\nd = 0\nans = 0\nfor i in range(n):\n    d = (a[i+1]-a[i])\n    ans =max(ans,d)\n    \nprint(k-ans)", "passed": true, "time": 0.14, "memory": 14080.0, "status": "done"}, {"code": "K,N=map(int,input().split())\nA=list(map(int,input().split()))\nans=K-(A[-1]-A[0])\nfor i in range(N-1):\n    tmp=A[i+1]-A[i]\n    ans=max(ans,tmp)\nans=K-ans\nprint(ans)", "passed": true, "time": 0.14, "memory": 14112.0, "status": "done"}, {"code": "#!/usr/local/bin/python3\n# https://atcoder.jp/contests/abc160/tasks/abc160_c\n\nK, N = list(map(int, input().split()))\nA = list(map(int, input().split()))\n\ndist = []\nfor i in range(N-1):\n    dist.append(A[i+1] - A[i])\ndist.append(K - A[-1] + A[0])\n\nprint((K - max(dist)))\n", "passed": true, "time": 0.14, "memory": 14260.0, "status": "done"}, {"code": "k,n = map(int,input().split())\na = list(map(int,input().split()))\n\na.sort()\na.append(a[0]+k)\n\nans = 0\nfor i in range(n):\n  d = a[i+1] - a[i]\n  ans = max(ans,d)\n\nprint(k - ans)", "passed": true, "time": 0.14, "memory": 14304.0, "status": "done"}, {"code": "K, N = list(map(int,input().split()))\nA = list(map(int,input().split()))\n\ndif = []\n\nfor i,a in enumerate(A[:len(A)-1]):\n    dif.append(A[i+1] - a)\n\ndif.append(K-A[len(A)-1] + A[0])\n\nprint((K - max(dif)))\n", "passed": true, "time": 0.2, "memory": 14108.0, "status": "done"}, {"code": "k,n=list(map(int,input().split()))\n\na=list(map(int,input().split()))\na.sort()\na.append(k+a[0])\n\nb=[0]*(n)\nfor i in range(n):\n    b[i]=a[i+1]-a[i]\n\nprint((k-max(b)))\n", "passed": true, "time": 0.14, "memory": 14120.0, "status": "done"}, {"code": "k,n = list(map(int,input().split()))\na = list(map(int,input().split()))\n\nb = []\nfor i in range(n-1):\n    b.append(a[i+1]-a[i])\n\nb.append(a[0]+(k-a[-1]))\n\nprint((sum(b)-max(b)))\n", "passed": true, "time": 0.14, "memory": 14252.0, "status": "done"}, {"code": "K,N = map(int,input().split())\nA1 = list(map(int,input().split()))\n\nD = [0] * (N)\n\nA2 = [A1[i]+K for i in range(len(A1)-1)]\nA1 = A1+A2\n\nfor i in range(N):\n    D[i] = A1[i+N-1] - A1[i]\n    #print(A1[i],A1[i+N-1])\nprint(min(D))", "passed": true, "time": 0.14, "memory": 14336.0, "status": "done"}, {"code": "k,n=map(int,input().split())\na=list(map(int,input().split()))\n\nc=[]\nfor i in range(1,n):\n    c.append(a[i]-a[i-1])\nc.append(k-a[-1]+a[0])\n\nprint(k-max(c))", "passed": true, "time": 0.23, "memory": 14232.0, "status": "done"}, {"code": "k, n = map(int, input().split())\nan = list(map(int, input().split()))\n\n\nclass Solution:\n    def __init__(self, k, n, an):\n        self.k = k\n        self.n = n\n        self.an = an\n\n    @staticmethod\n    def __append_first():\n        an.append(k + an[0])\n        new_an = an\n        return new_an\n\n    def answer(self):\n        new_an = self.__append_first()\n        max_length = 0\n        for i in range(n):\n            max_length = max(max_length, new_an[i + 1] - new_an[i])\n        print(k - max_length)\n\n\nconditions = Solution(k, n, an)\nconditions.answer()", "passed": true, "time": 0.14, "memory": 14128.0, "status": "done"}, {"code": "K,N = map(int,input().split())\nA = list(map(int,input().split()))\nsa = []\n\nfor i in range(N-1):\n  sa.append(A[i+1]-A[i])\n  \nsa.append((A[0]-A[N-1])%K)\n\nprint(K-max(sa))", "passed": true, "time": 0.14, "memory": 14112.0, "status": "done"}, {"code": "k, n = list(map(int, input().split()))\na = list(map(int, input().split()))\ndis = min(abs(a[0] - a[-1]), abs(k + a[0] - a[-1]))\nfor i in range(n-1):\n    dis = max(dis, abs(a[i+1] - a[i]))\nans = k - dis\nprint(ans)\n", "passed": true, "time": 0.14, "memory": 14256.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\nA = list(map(int, input().split()))\n\nA2 = [K+a for a in A]\nA3 = A + A2\n\ndist = [0] * N\nfor i in range(N):\n    j = i + N - 1\n    dist[i] = A3[j] - A[i]\n\nprint((min(dist)))\n\n", "passed": true, "time": 0.22, "memory": 14212.0, "status": "done"}, {"code": "def resolve():\n    k,n = map(int,input().split())\n    a = list(map(int,input().split()))\n    l = a[0]+k-a[-1]\n    for i in range(1,n):\n        l = max(l,a[i]-a[i-1])\n    print(k-l)\nresolve()", "passed": true, "time": 0.22, "memory": 14376.0, "status": "done"}, {"code": "# import numpy as np\n# import math\n\n# from scipy.special import perm : perm(n, r, exact=True)\n# from scipy.special import comb : comb(n, r, exact=True)\n\n# import itertools\n# for v in itertools.combinations(L, n):M.append(list(v))\n\n# from numba import njit\n# @njit('f8(i8,i8,i8,i8,f8[:,:,:])', cache=True)\n\n\n\"\"\" Definitions  \"\"\"\n\ndef lcm(a, b):\n    return a*b//math.gcd(a, b)\n\nMOD = 10**9+7\n\n# ============================================================\nk, n = list(map(int, input().split()))\nA = list(map(int, input().split()))\n\nm = 2*10**5\nM = [0]*n\ndist = min(A[n-1]-A[0], k-A[n-1]+A[0])\nfor i in range(n-1):\n    dist = max(dist, A[i+1]-A[i])\nprint((k-dist))\n", "passed": true, "time": 0.2, "memory": 14332.0, "status": "done"}, {"code": "l,n=map(int,input().split())\na=input().split()\nfor i in range(n):\n  a[i]=(int)(a[i])\n  \nmin=l+a[0]-a[n-1]\nfor i in range(n-1):\n  if min<a[i+1]-a[i]:\n    min=a[i+1]-a[i]\nprint(l-min)", "passed": true, "time": 0.19, "memory": 14048.0, "status": "done"}, {"code": "k, n = map(int,input().split())\na = list(map(int,input().split()))\n\nda =[-1] * n\nda[n-1] = k - a[n-1] + a[0]\nfor i in range(n-1):\n    da[i] = a[i+1] - a[i]\nprint(k-max(da))", "passed": true, "time": 0.14, "memory": 14168.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\nA = list(map(int, input().split()))\nans = 10**18\n\nfor i in range(N):\n    if i == 0:\n        clock_distance = A[N-1] - A[i]\n        reverse_distance = K - A[i+1] + A[i]\n    elif i == N-1:\n        clock_distance = K - A[i] + A[i-1]\n        reverse_distance = A[i] - A[0]\n    else:\n        clock_distance = K - A[i] + A[i+1]\n        reverse_distance = K - A[i+1] + A[i]\n    ans = min(clock_distance, reverse_distance, ans)\n\nprint(ans)\n\n\n\n", "passed": true, "time": 0.32, "memory": 14312.0, "status": "done"}, {"code": "f=lambda:[*map(int,input().split())]\nk,n=f()\nl=f()\nl+=[l[0]+k]\na=0\nfor i in range(n):\n  a=max(a,l[i+1]-l[i])\nprint(k-a)", "passed": true, "time": 0.42, "memory": 14068.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na = [int(s) for s in input().split()]\n\nd = [0] * (n + 1)\nd[0] = a[0] - 0\nfor i in range(1, n):\n    d[i] = a[i] - a[i - 1]\nd[n] = k - a[n - 1] + a[0]\nprint(k - max(d))", "passed": true, "time": 0.16, "memory": 14144.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na_list = list(map(int, input().split()))\nlongest = 0\nfor i in range(n):\n    if i==n-1:\n        longest = max(longest, k-a_list[i]+a_list[0])\n    else:\n        distance = a_list[i+1] - a_list[i]\n        longest = max(longest, distance)\nprint(k-longest)", "passed": true, "time": 0.14, "memory": 14100.0, "status": "done"}, {"code": "k,n = map(int,input().split())\na = list(map(int,input().split()))\nd= 0\nfor i in range(n-1):\n    d = max(a[i+1]-a[i],d)\nprint(min((k-d),a[-1]-a[0]))", "passed": true, "time": 0.15, "memory": 14264.0, "status": "done"}, {"code": "k,n = map(int,input().split())\nan = list(map(int,input().split()))\nan.append(k + an[0])\nmax_length = 0\nfor i in range(n):\n    max_length = max(max_length,an[i+1]-an[i])\n\nprint(k-max_length)", "passed": true, "time": 0.15, "memory": 14268.0, "status": "done"}, {"code": "K,N = map(int,input().split())\nA = list(map(int,input().split()))\n\nT = []\n\nfor i in range(1,N):\n    T.append(A[i] - A[i-1])\n\nT.append(K - A[N-1] + A[0])\n\nprint(sum(T)-max(T))", "passed": true, "time": 0.23, "memory": 14112.0, "status": "done"}, {"code": "k,n=map(int,input().split())\na=list(map(int,input().split()))\n\nn=len(a)-1\ncnt=[a[n]-a[0]]\nfor i in range(n) :\n    cnt.append(k-(a[i+1]-a[i]))\nans=min(cnt)\n\nprint(ans)", "passed": true, "time": 0.14, "memory": 14308.0, "status": "done"}, {"code": "\nk, n = map(int, input().split())\na = list(map(int, input().split()))\n\nc = a[0]\na.append(c + k)\nb = [a[i+1] - a[i] for i in range(n)]\n\nprint(k - max(b))", "passed": true, "time": 0.14, "memory": 14116.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na = list(map(int, input().split()))\n\nd = [0]*n\nfor i in range(n):\n    if i == n-1:\n        d[n-1] = (k-a[n-1]) + a[0]\n        \n    else :\n        d[i] = a[i+1] - a[i]\n\nd.sort()\nd[n-1] = 0\n\nprint(sum(d))", "passed": true, "time": 0.14, "memory": 14076.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\nA = list(map(int, input().split()))\n\nA3 = A + [K+a for a in A]\ndist = [A3[i+N-1] - A[i] for i in range(N)]\n\nprint((min(dist)))\n\n", "passed": true, "time": 0.14, "memory": 14260.0, "status": "done"}, {"code": "k, n = list(map(int,input().split()))\na = list(map(int,input().split()))\nnew_a = sorted(a)\nnum = len(new_a) - 1\ns_a = []\nb = (k - new_a[num]) + new_a[0]\ns_a.append(b)\ncun = 0\nfor i in new_a[1::]:\n    s = i - new_a[cun]\n    s_a.append(s)\n    cun += 1\nmax_num = max(s_a)\nprint((sum(s_a) - max_num))\n\n", "passed": true, "time": 0.14, "memory": 14344.0, "status": "done"}, {"code": "def __starting_point():\n\n    k,n = list(map(int,input().split()))\n    A = list(map(int,input().split()))\n\n    #\u8ddd\u96e2\u306e\u5dee\u5206\u304c\u4e00\u756a\u591a\u3044\u533a\u9593\u3092\u6c42\u3081\u308b\n    sbn = -1\n    for i in range(n-1):\n        sbn = max(sbn,A[i+1]-A[i])\n\n    #\u6700\u521d\u3068\u6700\u5f8c\u3082\u6bd4\u8f03\u3059\u308b\n    tmp1 = A[0] - 0\n    tmp2 = k - A[n-1]\n    sbn = max(sbn,tmp1+tmp2)\n\n    print((k-sbn))\n\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14096.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA = list(map(int, input().split()))\nA.append(K+A[0])\n\nmax_dist = max([A[i+1] - A[i] for i in range(N)])\nprint(K - max_dist)", "passed": true, "time": 0.14, "memory": 14172.0, "status": "done"}, {"code": "k, n = list(map(int, input().split()))\na = [0] + list(map(int, input().split()))\n\nd_max = 0\na[0] = a[n] - k\n\nfor i in range(1, n + 1):\n    d = a[i] - a[i - 1]\n    d_max = max(d, d_max)\n\nprint((k - d_max))\n", "passed": true, "time": 0.14, "memory": 14088.0, "status": "done"}, {"code": "k, n = map(int, input().split())\nan = [int(num) for num in input().split()]\n\ndistance =[]\nfor i in range(n-1):\n  distance.append(an[i+1]-an[i])\ndistance.append(an[0]+(k-an[n-1]))\n\ndistance.sort()\nprint(k-distance[n-1])", "passed": true, "time": 0.14, "memory": 14312.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA = list(map(int, input().split()))\n\nB = []\nfor i in range(N-1):\n  B.append(A[i+1] - A[i])\nB.append(K - A[N-1] + A[0])\nans = K - max(B)\nprint(ans)", "passed": true, "time": 0.14, "memory": 14120.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA = list(map(int, input().split()))\n\nsub = [0] * (N - 1)\n\nfor i in range(N - 1):\n\tsub[i] = A[i + 1] - A[i]\nsub.append(A[0] + (K - A[-1]))\n\nprint(sum(sub) - max(sub))", "passed": true, "time": 0.14, "memory": 14336.0, "status": "done"}, {"code": "k,n = map(int,input().split())\na = list(map(int,input().split()))\nans = k\nmx = k-a[-1]+a[0]\nfor i in range(n-1):\n  mx = max(mx,abs(a[i]-a[i+1]))\nprint(ans-mx)", "passed": true, "time": 0.14, "memory": 14232.0, "status": "done"}, {"code": "k,n = map(int,input().split())\na = list(map(int,input().split()))\ndd = k-a[-1]+a[0]\nd = 0\nfor i in range(n-1):\n    d = max(d,a[i+1]-a[i])\nd = max(d,dd)\nprint(k-d)", "passed": true, "time": 0.14, "memory": 14260.0, "status": "done"}, {"code": "K, N = map(int, input().split(' '))\nA_ls = list(map(int, input().split(' ')))\nrst = -1\nfor i in range(N):\n    l = A_ls[(i + 1) % N] - A_ls[i]\n    if l < 0:\n        l = K - A_ls[i] + A_ls[(i + 1) % N]\n    if rst == -1:\n        rst = l\n    else:\n        rst = max(rst, l)\nprint(K - rst)", "passed": true, "time": 0.28, "memory": 14064.0, "status": "done"}, {"code": "K,N=list(map(int,input().split()))\nA=list(map(int,input().split()))\nans=A[0]+K-A[-1]\nfor i in range(N-1):\n    ans=max(ans,A[i+1]-A[i])\nprint((K-ans))\n", "passed": true, "time": 0.28, "memory": 14164.0, "status": "done"}, {"code": "k, n = list(map(int, input().split()))\ncnt = [0] * (n + 1)\ncmb = 0\na = list(map(int, input().split()))\n\nans = 10 ** 6 + 1\nfor i in range(n):\n  r_idx = ((i+1)%n)\n  r_ans = a[i]+(k-a[r_idx]) if a[i] < a[r_idx] else abs(a[r_idx]-a[i])\n  l_idx = (i-1+n)%n\n  l_ans = (k-a[i])+a[l_idx] if a[i] > a[l_idx] else a[l_idx]-a[i]\n\n  ans = min([ans, r_ans, l_ans])\n\nprint(ans)\n", "passed": true, "time": 0.14, "memory": 14224.0, "status": "done"}, {"code": "k,n=map(int,input().split());a,c=[*map(int,input().split())],[0]*n\nfor i in range(n-1):\n  c[i]=a[i+1]-a[i]\nc[-1]=a[0]+k-a[-1]\nprint(k-max(c))", "passed": true, "time": 0.14, "memory": 14136.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA = [int(i) for i in input().split()]\nA.append(A[0] + K)\nmax = 0\nfor i in range(N):\n\tif max <= (A[i+1] - A[i]):\n\t\tmax = A[i+1] - A[i]\n    \nprint(K - max)", "passed": true, "time": 0.14, "memory": 14152.0, "status": "done"}, {"code": "K, N = list(map(int,input().split()))\nA    = list(map(int,input().split()))\nA.sort()\nd = [A[i+1]-A[i] for i in range(N-1)]\nd.append(A[0]+K-A[-1])\nprint(K-max(d))", "passed": true, "time": 0.14, "memory": 14080.0, "status": "done"}, {"code": "k,n=map(int,input().split());a=[*map(int,input().split())];d=[0]*n\nfor i in range(n-1):\n  d[i]=a[i+1]-a[i]\nd[-1]=a[0]+k-a[-1]\nprint(k-max(d))", "passed": true, "time": 0.14, "memory": 14296.0, "status": "done"}, {"code": "k, n = list(map(int, input().split()))\na = list(map(int, input().split()))\na1 = sorted(a)\ntemp = list()\nx = len(a)-1\nfor i in range(x):\n    temp.append(a1[i+1]-a1[i])\ntemp.append(min(max(a)-min(a),k-max(a)+min(a)))\nans = k-max(temp)\nprint(ans)\n", "passed": true, "time": 0.15, "memory": 14360.0, "status": "done"}, {"code": "k, n = map(int, input().split())\na = list(map(int, input().split()))\n\nbef = a[0]\nmax_diff = 0\nfor i in range(1,n):\n    diff = abs(bef - a[i])\n    max_diff = max(diff, max_diff)\n    bef = a[i]\n\nprint(k - max(max_diff, k - abs(a[n-1] - a[0])))", "passed": true, "time": 0.14, "memory": 14304.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\nA = [int(x) for x in input().split()]\n\nmx = A[0] + K - A[-1]\n\nfor i in range(len(A) - 1):\n    dis = A[i + 1] - A[i]\n    if dis > mx:\n        mx = dis\n\nprint((K - mx))\n", "passed": true, "time": 0.14, "memory": 14284.0, "status": "done"}, {"code": "K, N = list(map(int, input().split()))\nA = list(map(int, input().split()))\n\n\n\nA = sorted(A)\nL = []\nANS = 0\n\nA_max = max(A)\n\nfor i in range(N-1):\n    L.append(abs(A[i+1]-A[i]))\n        \nL.append(K + A[0] - A_max)\n\nL = sorted(L)\n\n\nL.pop(-1)\n\nfor i in range(len(L)):\n    ANS = ANS + L[i]\n    \nprint(ANS)\n", "passed": true, "time": 0.14, "memory": 14168.0, "status": "done"}, {"code": "k,n = map(int, input().split())\nA = list(map(int,input().split()))\nd = 0\n\nfor i in range(n-1) :\n    d = max(d, A[i+1] - A[i])\n\nd1 = (k - A[n-1]) + A[0]\nd = max(d, d1)\nprint(k-d)", "passed": true, "time": 0.14, "memory": 14184.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA = [int(a) for a in input().split()]\nA.append(A[0] + K)\nb = []\nmax = 0\nsum = 0\nfor i in range(N):\n    t = A[i+1] - A[i]\n    sum += t\n    if max < t:\n        max = t\nsum -= max\nprint(sum)", "passed": true, "time": 0.14, "memory": 14332.0, "status": "done"}, {"code": "K, N = map(int, input().split())\nA = list(map(int, input().split()))\n\nnums = [0] * N\nfor i in range(N - 1):\n    nums[i] = A[i + 1] - A[i]\nnums[-1] = K + A[0] - A[-1]\n\nprint(sum(nums) - max(nums))\nreturn", "passed": true, "time": 0.14, "memory": 14144.0, "status": "done"}]