CodeEff/ECCO huggingface dataset:
# Original solution
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))

dA = []
for i in range(1, N):
    dA.append(A[i] - A[i-1])
    if i == N - 1:
        dA.append(A[0] - (A[i] - K))

dA = sorted(dA)
print((sum(dA[:N-1])))

# Optimized solution
# C - Traveling Salesman around Lake
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))

dist = []
for i in range(N-1):
    dist.append(abs(A[i] - A[i+1]))
dist.append(abs(K - A[-1] + A[0]))
dist = sorted(dist, reverse=True)
print((sum(dist[1:])))
# Original solution
K, N = tuple(int(v) for v in input().split())

A_list = tuple(int(a) for a in input().split())

# 各点の距離
x_iter = iter(A_list)
y_iter = iter(A_list)
next(y_iter)

d_list = [y - x for x, y in zip(x_iter, y_iter)]
d_list.append(K - A_list[-1] + A_list[0])
d_list += d_list

l = len(d_list) // 2
sum_d = [sum(d_list[i:i+l-1]) for i in range(l)]

print((min(sum_d)))


# Optimized solution
K, N = tuple(int(v) for v in input().split())

A_list = list(int(a) for a in input().split())

# # 各点の距離
# x_iter = iter(A_list)
# y_iter = iter(A_list)
# next(y_iter)
# 
# d_list = [y - x for x, y in zip(x_iter, y_iter)]
# d_list.append(K - A_list[-1] + A_list[0])
# d_list += d_list
# 
# l = len(d_list) // 2
# # sum_d = [sum(d_list[i:i+l-1]) for i in range(l)]
# min_d = min(sum(d_list[i:i+l-1]) for i in range(l))
# 
# print(min_d)

A_list += [a + K for a in A_list[:-1]]
print((min(A_list[i+N-1] - A_list[i] for i in range(N))))
# Original solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
a2 = a + [aa + k for aa in a]
max_inter = 0
for i in range(n*2 - 1):
    max_inter = max(max_inter, a2[i+1] - a2[i])
print((k - max_inter))

# Optimized solution
k, n = list(map(int, input().split()))
arr = list(map(int, input().split()))
max_inter = 0
max_inter = max(max_inter, arr[0]+k - arr[-1])
for i in range(n-1):
    max_inter = max(max_inter, arr[i+1] - arr[i])
print((k - max_inter))
# Original solution
inputs = [int(i) for i in input().split()]
K,N = inputs[0],inputs[1]

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

max_range = input_lines[0]+(K-input_lines[-1])
for i in range(N):
    if i!=N-1:
        torange = input_lines[i+1]-input_lines[i]
        if torange>max_range:
            max_range = torange
print((K-max_range))


# Optimized solution
k,n = list(map(int,input().split()))
a_inputs = [int(a) for a in input().split()]

longest = a_inputs[0]+(k-a_inputs[-1])
for i in range(n-1):
    if a_inputs[i+1]-a_inputs[i]>longest:
        longest = a_inputs[i+1]-a_inputs[i]

print((k-longest))
# Original solution
def solve():
    K, N = list(map(int, input().split()))
    A = list(map(int, input().split()))

    # 距離の最大値を求める．
    max_dist = 0
    for i in range(N):
        for j in range(N):
            # 時計回りの距離
            dist1 = abs(A[i] - A[j])
            # 反時計回りの距離
            dist2 = K - dist1
            if(dist1 < dist2):
                dist_tmp = dist1
                flg = True
            else:
                dist_tmp = dist2
                flg = False
            if(dist_tmp > max_dist):
                max_dist = dist_tmp
                max_index = i, j
                max_flg = flg
    k = 0
    for k in range(N):
        if(k == max_index[0] or k == max_index[1]):
            continue
        if(abs(A[max_index[0]] - A[k] <= max_dist and  abs(A[max_index[1]] - A[k] <= max_dist))):
            if(flg):
                ans = max_dist
            else:
                ans = K - max_dist
        else:
            if(flg):
                ans = K - max_dist
            else:
                ans = max_dist
        break
    print(ans)


if __name__ == "__main__":
    solve()

# Optimized solution
def solve():
    K, N = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort()

    max_dist = 0
    for i in range(1, N):
        dist_tmp = A[i] - A[i-1]
        if(dist_tmp > max_dist):
            max_dist = dist_tmp
    dist_over_zero = K - (A[N-1] - A[0])
    if(dist_over_zero > max_dist):
        ans = K - dist_over_zero
    else:
        ans = K - max_dist
    print(ans)


if __name__ == "__main__":
    solve()
# Original solution
# -*- coding: utf-8 -*-
data = input().split()

round = int(data[0])
cnt_house = int(data[1])

distance = input().split()

min_dist = None

for start in range(cnt_house):
  move_dist = 0
    
  for i in range(cnt_house - 1):
    if start + i == cnt_house - 1:
      move_dist += round - int(distance[start + i]) + int(distance[start + i - cnt_house + 1])
    elif start + i < cnt_house - 1:
      move_dist += int(distance[start + i + 1]) - int(distance[start + i])
    else:
      move_dist += int(distance[start + i - cnt_house + 1]) - int(distance[start + i - cnt_house])
    
    if min_dist is not None and min_dist < move_dist:
      break
  
  if min_dist is None or min_dist > move_dist:
    min_dist = move_dist

print(min_dist)

# Optimized solution
# -*- coding: utf-8 -*-
data = input().split()

round = int(data[0])
cnt_house = int(data[1])

distance = input().split()

min_dist = None

for start in range(cnt_house):
  if start == 0:
    move_dist = int(distance[cnt_house - 1]) - int(distance[start])
  else:
    move_dist = (round - int(distance[start])) + int(distance[start - 1])
  
  if min_dist is None or min_dist > move_dist:
    min_dist = move_dist

print(min_dist)
# Original solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))

all_length = k*2
point = []
for i in range(n):
    a_left  = k-a[i]
    a_right = k+a[i]
    point.append(a_left)
    point.append(a_right)
point = list(set(point))
point.sort()

num = len(point)
num = round(num/2)
distance = []
for i in range(num):
    dis = 0
    for j in range(n-1):
        dis += point[i+j+1] - point[i+j]
    distance.append(dis)
mindis = min(distance)
print(mindis)

# Optimized solution
k, n = list(map(int, input().split()))
A = list(map(int, input().split()))

A.append(A[0]+k)
l = 0
for i in range(n):
    l = max(l, A[i+1]-A[i])
print((k-l))
# Original solution
from collections import deque
K, N = list(map(int, input().split()))
A = deque(list(map(int, input().split())))
A.appendleft(K - A[-1] + A[0])
sa_max = A[0]
for i in range(1, N):
    sa = A[i + 1] - A[i]
    if sa_max < sa:
        sa_max = sa
print((A[-1] + A[0] - (sa_max + A[1])))


# Optimized solution
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
A.append(K - A[-1] + A[0])
sa_max = A[-1]
for i in range(N - 1):
    sa = A[i + 1] - A[i]
    if sa_max < sa:
        sa_max = sa
print(((A[-2] - A[0]) + A[-1] - sa_max))
# Original solution
K, N = list(map(int,input().split()))
A = list(map(int, input().split()))
l = 0
L = []
for i in range(N-1):
  l = A[i+1] - A[i]
  L.append(l)
L.append(K-A[N-1]+A[0])
Ans = []
for j in range(len(L)):
  l = sum(L) - L[j]
  Ans.append(l)
print((min(Ans)))


# Optimized solution
K, N = list(map(int,input().split()))
A = list(map(int, input().split()))
l = 0
L = []
for i in range(N-1):
  l = A[i+1] - A[i]
  L.append(l)
L.append(K-A[N-1]+A[0])
print((sum(L)-max(L)))
# Original solution
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
maxd = (K - A[-1]) + A[0]
for i in range(1, N):
    d = A[i] - A[i - 1]
    maxd = max(maxd, d)
print((K - maxd))

# Optimized solution
K, N = list(map(int, input().split()))
A = tuple(map(int, input().split()))

maxd = K - A[-1] + A[0]
for i in range(1, N):
    d = A[i] - A[i-1]
    maxd = max(maxd, d)
ans = K - maxd
print(ans)
# Original solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))

d = [a[i] - a[i-1] for i in range(1, n)]
d.insert(0, a[0])
d.append(k - a[-1])
sum_d = sum(d)

most_min_path = 10000

for i in range(n):
    if i == 0:
        normal_ck = sum_d - d[i] - d[-1]
        reverse_ck = sum_d - d[i+1]
    elif i == n - 1:
        normal_ck = sum_d - d[i]
        reverse_ck = sum_d - d[i+1] - d[0]
    elif 0 < i < n - 1:
        normal_ck = sum(d) - d[i]
        reverse_ck = sum(d) - d[i+1]

    min_ck = normal_ck if normal_ck < reverse_ck else reverse_ck
    if most_min_path > min_ck:
        most_min_path = min_ck

print(most_min_path)

# Optimized solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
a.append(a[0] + k)

d = [a[i+1] - a[i] for i in range(n)]
l = 0
for i in range(n):
    l = max(l, a[i+1] - a[i])
print((k - l))
# Original solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
a.append(a[0] + k)

d = [a[i+1] - a[i] for i in range(n)]
l = 0
for i in range(n):
    l = max(l, a[i+1] - a[i])
print((k - l))

# Optimized solution
def main():
    k, n = list(map(int, input().split()))
    a = list(map(int, input().split()))
    a.append(a[0] + k)

    max_length = 0
    for i in range(n):
        max_length = max(max_length, a[i+1] - a[i])

    print((k - max_length))


if __name__ == '__main__':
    main()
# Original solution
K,N=list(map(int,input().split()))
A=list(map(int,input().split()))
ans=0
for i in range(N):
    for j in range(N):
        C=abs(A[i]-A[j])
        D=K-C
        if C>D:
            saidai=D
        else:
            saidai=C
        if ans<saidai:
            ans=saidai
        else:
            pass
print(ans)


# Optimized solution
K,N=list(map(int,input().split()))
A=list(map(int,input().split()))

dis=A[0]+K-A[N-1]

for i in range(N-1):
    if A[i+1]-A[i]>=dis:
        dis=A[i+1]-A[i]
    else:
        pass

print((K-dis))
# Original solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))

a += [k]
x = [a[i+1]-a[i] for i in range(n)]


answer = sum(x)
for i in range(n):
    _x = x[:i] + x[i+1:]
    answer = min(answer, sum(_x))
print(answer) 

# Optimized solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
a += [k]
x = [a[0]]
for i in range(n):
    _a = a[i+1] - a[i]
    x += [_a]
x[0] = x[0]+x[-1]
x = x[:-1]
x.remove(max(x))
print((sum(x)))
# Original solution
k,n=list(map(int,input().split()))
a=list(map(int,input().split()))
m=0
for i in range(n):
    for j in range(i+1,n):
        l=min(a[j]-a[i],k-a[j]+a[i])
        m=max(m,l)
print((k-m))

# Optimized solution
k,n=list(map(int,input().split()))
a=list(map(int,input().split()))
m=0
for i in range(n-1):
    m=max(m,a[i+1]-a[i])
m=max(m,k-a[n-1]+a[0])
print((k-m))
# Original solution
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))

distance = []

for i in range(N-1):
    dis = A[i + 1] - A[i]
    # if i == N - 1:
    #     dis = A[i] - A[1]
    distance.append(dis)

dis = K - A[N - 1] + A[0]
distance.append(dis)

# print(distance)
# print(max(distance))
# print(distance.index(max(distance)))

sum = 0

count = int(len(distance))

for i in range(count):
    if i != distance.index(max(distance)):
        sum += distance[i]

print(sum)

# Optimized solution
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))

distance = []

for i in range(N-1):
    dis = A[i + 1] - A[i]
    distance.append(dis)

dis = K - A[N - 1] + A[0]
distance.append(dis)

index = distance.index(max(distance))

print((K - distance[index]))
# Original solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))

res = []
for i in range(n-1):
  j = a[i+1] - a[i]
  res.append(j)
l = k + a[0] - a[n-1]
res.append(l)
m = max(res)
print((k - m))

# Optimized solution
k,n=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
data=[0]*n
for i in range(n-1):
  data[i]=a[i+1]-a[i]
data[n-1]=k+a[0]-a[n-1]
print((sum(data)-max(data)))
# Original solution
K,N=list(map(int,input().split()))
A=list(map(int,input().split()))
distance=max(A)-min(A)
for i in range(N):
    A.append(A[i]+K)
for i in range(N):
    distance=min(distance,A[i+N-1]-A[i])
print(distance)

# Optimized solution
K,N=list(map(int,input().split()))
A=list(map(int,input().split()))
A+=[A[0]+K]
print((min(K-(A[i+1]-A[i]) for i in range(N))))
# Original solution
import sys
read = sys.stdin.buffer.read
k, n, *A = list(map(int, read().split()))
far = k + A[0] - A[-1]
for x, y in zip(A[1:], A):
    if far < x - y:
        far = x - y
print((k-far))

# Optimized solution
import sys
read = sys.stdin.buffer.read
k, n, *A = list(map(int, read().split()))
far = k + A[0] - A[-1]
y = A[0]
for x in A:
    if far < x - y:
        far = x - y
    y = x
print((k-far))
# Original solution
import sys
read = sys.stdin.buffer.read
k, n, *A = list(map(int, read().split()))
far = k + A[0] - A[-1]
y = A[0]
for x in A[1:]:
    dis = x - y
    if far < dis:
        far = dis
    y = x
print((k - far))

# Optimized solution
import sys


def main():
    read = sys.stdin.buffer.read
    k, n, *A = list(map(int, read().split()))
    far = k + A[0] - A[-1]
    y = A[0]
    for x in A[1:]:
        dis = x - y
        if far < dis:
            far = dis
        y = x
    print((k - far))


if __name__ == "__main__":
    main()
# Original solution
import sys


def main():
    read = sys.stdin.buffer.read
    k, n, *A = list(map(int, read().split()))
    A += [k + A[0]]
    far = max(x - y for x, y in zip(A[1:], A))
    print((k - far))


if __name__ == "__main__":
    main()

# Optimized solution
import sys


def main():
    read = sys.stdin.buffer.read

    k, n, *A = list(map(int, read().split()))
    A += [A[0] + k]
    far = max(y - x for x, y in zip(A, A[1:]))
    print((k - far))


if __name__ == "__main__":
    main()
# Original solution
import itertools
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))

A_list = list(itertools.permutations(A, N))
ans = 10**8
for i in A_list:
    tmp = 0
    
    if (i[0] == min(A) and i[2] == max(A)) or  (i[0] == max(A) and i[2] == min(A)):
        for j in range(N-1):
            if abs((i[j+1]) - (i[j])) <= abs(K-i[j+1]):
                tmp = tmp +  abs((i[j+1]) - (i[j]))
            else:
                tmp = tmp + abs(K-i[j+1])
        
        if tmp <= ans:
            ans = tmp
    else:
        pass
print(ans)

# Optimized solution
K,N = list(map(int, input().split()))
A = [int(a) for a in input().split()]

ans = A[-1]-A[0]
for i in range(N-1):
    ans = min(ans, K-A[i+1]+A[i])
print(ans)
# Original solution
K,N = list(map(int,input().split()))
L = [i for i in map(int,input().split())]
L.append(L[0]+K)
dist = []
for i in range(N):
    dist.append(abs(L[i+1]-L[i]))
print((sum(dist)-max(dist)))

# Optimized solution
K,N = list(map(int,input().split()))
L = [i for i in map(int,input().split())]
L.append(L[0]+K)
dist = []
for i in range(N):
    dist.append(L[i+1]-L[i])
print((sum(dist)-max(dist)))
# Original solution
K,N=list(map(int, input().split()))
A=list(map(int, input().split()))
max_diff = 0
for i in range(0,N):
    for j in range(i,N):
        ck = abs(A[j] - A[i])
        if max_diff < ck:
            if ck <= K/2:
                max_diff = ck
print(max_diff)


# Optimized solution
K,N=list(map(int, input().split()))
A=list(map(int, input().split()))
max_diff = 0
ck = 0
for i in range(0,N):
    if i == N -1:
        ck = abs(A[(i+1)%N] + K  - A[i])
    else:
        ck = abs(A[(i+1)%N] - A[i])
    if max_diff < ck:
        max_diff = ck
print((K - max_diff))
# Original solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
d = [0] * n
d_max = 0

for i in range(n - 1):
    d[i] = a[i + 1] - a[i]
    d_max = max(d_max, d[i])

d[-1] = (k - a[-1]) + a[0]
d_max = max(d_max, d[-1])

print((k - d_max))


# Optimized solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
d_max = 0

for i in range(n - 1):
    d = a[i + 1] - a[i]
    d_max = max(d_max, d)

d = (k - a[-1]) + a[0]
d_max = max(d_max, d)

print((k - d_max))
# Original solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
d_max = 0

for i in range(n - 1):
    d = a[i + 1] - a[i]
    d_max = max(d_max, d)

d = (k - a[-1]) + a[0]
d_max = max(d_max, d)

print((k - d_max))


# Optimized solution
k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
d_max = 0

for i in range(n - 1):
    d = a[i + 1] - a[i]
    if d > d_max:
        d_max = d

d = (k - a[-1]) + a[0]
if d > d_max:
    d_max = d

print((k - d_max))
# Original solution
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    K, N = il()
    A = il()
    A.sort()
    ret = max(A) - min(A)

    for n in range(N - 1):
        mi = min(A)
        tmp = abs(A[n] - mi) + (K - A[n + 1])
        ret = min(ret, tmp)

    print(ret)


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    K, N = il()
    A = il()
    A.sort()
    ret = max(A) - min(A)

    for n in range(N - 1):
        ret = min(ret, A[n] + (K - A[n + 1]))

    print(ret)


if __name__ == '__main__':
    main()
# Original solution
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
dist = 0
for a in A:
    dist |= 1 << a
dist = format(dist, "0%db" % K)
d = dist.index("1")
ans = 0
count = 0
for i in range(K):
    if dist[(d + i) % K] == "1":
        ans = max(ans, count)
        count = 0
    else:
        count += 1
ans = max(ans, count)
print((K - ans - 1))

# Optimized solution
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
dist = [0] * K
for a in A:
    dist[a] = 1
d = dist.index(1)
ans = 0
count = 0
for i in range(K):
    if dist[(d + i) % K] == 1:
        ans = max(ans, count)
        count = 0
    else:
        count += 1
ans = max(ans, count)
print((K - ans - 1))
# Original solution
K, N = [ int(i) for i in input().split()]

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

for i in range(0, N):
  distances = n
  if i > 0:
    distances[i-1] += K
    
  total.append(max(distances) - distances[i])
  
print((min(total)))

# Optimized solution
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
 
A.append(A[0]+K)
maxD = 0
 
for n in range(0, N):
  maxD = max(maxD, A[n+1] - A[n])
  
print((K - maxD))
# Original solution
K, N = list(map(int, input().split()))
Alist = list(map(int, input().split()))
  
#for each house, traverse clock/anti-clock wise
Alen = len(Alist)
min_distance = 10000000
for s in range(Alen):
  distance = 0
  start_p = s
  current_p = s
  next_p = 0 # random number
  #clock-wise
  while (True):
    # calculate next point
    if (current_p == (Alen-1)):
      next_p = 0
    else:
      next_p = current_p+1
    # finish if reached to start point again
    if (next_p == start_p):
      break
    # add distance from current to next point
    if (next_p == 0):
      distance += (K-Alist[current_p]+Alist[next_p])
    else:
      distance += (Alist[next_p]-Alist[current_p])
    # move to next point
    current_p = next_p
   
  if (distance < min_distance):
    min_distance = distance
  #anti- clock-wise
  #distance = 0
  #while (True):
  #  if (s == 0):
   #   distance += (Alist[s]+(K-Alist[s-1]))
   # else:
   #   distance += (Alist[s]-Alist[s-1])
   # s -= 1
  #  if ( (s-1) == ((-1*Alen)+start_p) ):
   #   break
 # print("anti"+str(distance))
  #if (distance < min_distance):
   # min_distance = distance

print(min_distance)
      

# Optimized solution
K, N = list(map(int, input().split()))
Alist = list(map(int, input().split()))
  
#for each house, traverse clock/anti-clock wise
Alen = len(Alist)
min_distance = 10000000
for s in range(Alen):
  distance = 0
  current_p = s
  #clock-wise distance
  if (current_p == (Alen-1)):
    next_p = 0
    distance = Alist[current_p]-Alist[next_p]
  else:
    next_p = current_p+1
    distance = K-(Alist[next_p]-Alist[current_p])
  if (distance < min_distance):
    min_distance = distance
  #anti clock-wise distance
  if (current_p == 0):
    next_p = Alen-1
    distance = Alist[next_p]-Alist[current_p]
  else:
    next_p = current_p-1
    distance = K-(Alist[next_p]-Alist[current_p])
  if (distance < min_distance):
    min_distance = distance
print(min_distance)
# Original solution
K, N  = list(map(int,input().split()))
As = list(map(int, input().split()))

distList = []

for idx, dist in enumerate(As):
  if idx == 0:
    distList.append(K - As[-1] + dist)
  else:
    distList.append(dist - As[idx - 1])

min_dist = 0
for idx, dist in enumerate(distList):
  target_dist = 0
  for i in range(N - 1):
    if idx == 0:
      target_dist += distList[idx - i]
      min_dist = target_dist
    else:
      target_dist += distList[idx - i]
  if target_dist < min_dist:
    min_dist = target_dist
print(min_dist)

# Optimized solution
K, N  = list(map(int,input().split()))
As = list(map(int, input().split()))

As.append(K + As[0])
print((K - max([y - x for x,y in zip(As, As[1:])])))
# Original solution
K, N=list(map(int, input().split()))
A=list(map(int, input().split()))

box = []
for i in range(N):
    a = abs(A[i-1]-A[i])
    if a>K/2:
        a = K - a
    box.append(a)
box.extend(box)
dis = []
for i in range(N):
    d = sum(box[i:i+N-1])
    dis.append(d)

print((min(dis)))

# Optimized solution
K, N=list(map(int, input().split()))
A=list(map(int, input().split()))

box = []
for i in range(N):
    d = abs(A[i-1]-A[i])
    if d>K/2:
        d = K - d
    box.append(d)
print((K-max(box)))
# Original solution
K, N = list(map(int, input().split()))
loc = list(map(int, input().split()))
distances = []
total = []

for i in range(N-1):
    distances.append(loc[i+1] - loc[i])

distances.append(loc[0] + K - loc[N-1])

for i in range(N):
    total.append(K - distances[i])

print((min(total)))


# Optimized solution
K, N = list(map(int, input().split()))
loc = list(map(int, input().split()))
distances = []
total = []

for i in range(N-1):
    distances.append(loc[i+1] - loc[i])

distances.append(loc[0] + K - loc[N-1])
max_dis = max(distances)

print((K - max_dis))
# Original solution
k, n = list(map(int,input().split()))
xs = list(map(int,input().split()))
xs = xs + [x+k for x in xs]

ans = float('inf')
for i in range(n):
    a = xs[i:i+n]
    delta = a[-1] - a[0]
    ans = min(delta, ans)

print(ans)

# Optimized solution
k, n = list(map(int,input().split()))
xs = list(map(int,input().split()))
xs = xs + [x+k for x in xs]

ans = float('inf')
for i in range(n):
    delta = xs[i+n-1] - xs[i]
    ans = min(delta, ans)

print(ans)
# Original solution
k,n = list(map(int, input().split()))
a = list(map(int, input().split()))
a = a + [a[0]+k]
dif = [0]*n
for i in range(n):
    dif[i] += a[i+1] - a[i]

dif.sort()
print((k-dif[-1]))

# Optimized solution
k,n = list(map(int, input().split()))
a = list(map(int, input().split()))
a = a + [a[0]+k]
dif = [0]*n
for i in range(n):
    dif[i] += a[i+1] - a[i]
print((k-max(dif)))
# Original solution
k,n,*a=list(map(int,open(0).read().split()))
a+=a[0]+k,
print((min(k-a[i+1]+a[i]for i in range(n))))

# Optimized solution
k,n,*l=list(map(int,open(0).read().split()))
print((min((l[i-1]-l[i])%k for i in range(n))))
# Original solution
K, N  = list(map(int,input().split()))
List = list(map(int,input().split()))
d = []
for i in range(N):
  for j in range(N):
    x = min(abs(List[i]-List[j]), K-abs(List[i]-List[j]))
    d.append(x)
result = K - int(max(d))
print(result)

# Optimized solution
K, N  = list(map(int,input().split()))
List = list(map(int,input().split()))
d = []
for i in range(1,N):
  x = min(abs(List[i]-List[i-1]), K-abs(List[i]-List[i-1]))
  d.append(x)
d.append(min(abs(List[N-1]-List[0]), K-abs(List[N-1]-List[0])))
result = K - int(max(d))
print(result)