AtCoder Beginner Contest 160 - Traveling Salesman around Lake

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.

Source: atcoder | Difficulty: EASY


Solutions:
(k, n, *a) = map(int, open(0).read().split())
a.append(k + a[0])
b = [a[i + 1] - a[i] for i in range(n)]
print(k - max(b))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
b = [a[i] - a[i - 1] for i in range(1, n)]
b.append(k - a[-1] + a[0])
print(k - max(b))


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
sub = [0] * (N - 1)
for i in range(N - 1):
	sub[i] = A[i + 1] - A[i]
sub.append(A[0] + (K - A[-1]))
print(sum(sub) - max(sub))


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
L = 0
for i in range(N - 1):
	L = max(L, A[i + 1] - A[i])
L = max(L, K - A[-1] + A[0])
print(K - L)


(k, n, *a) = map(int, open(0).read().split())
l = k - a[n - 1] + a[0]
for i in range(n - 1):
	l = max(l, a[i + 1] - a[i])
print(k - l)


def __starting_point():
	(K, N) = map(int, input().split())
	li = list(map(int, input().split()))
	li.append(K + li[0])
	l = 0
	for i in range(N):
		l = max(l, abs(li[i] - li[i + 1]))
	print(K - l)
__starting_point()


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
d = []
for i in range(N - 1):
	d.append(A[i + 1] - A[i])
d.append(A[0] + K - A[N - 1])
max_d = max(d)
print(K - max_d)


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
kankaku = [(a[i] - a[i - 1]) % k for i in range(len(a))]
print(k - max(kankaku))


(K, N) = [int(i) for i in input().split()]
A = sorted([int(i) for i in input().split()])
A += [A[0] + K]
print(K - max((y - x for (x, y) in zip(A, A[1:]))))


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


def __starting_point():
	(k, n) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	sbn = -1
	for i in range(n - 1):
		sbn = max(sbn, A[i + 1] - A[i])
	tmp1 = A[0] - 0
	tmp2 = k - A[n - 1]
	sbn = max(sbn, tmp1 + tmp2)
	print(k - sbn)
__starting_point()


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
l = A[-1] - A[0]
for i in range(N - 1):
	l = min(l, K - A[i + 1] + A[i])
print(l)


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


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


(n, k) = map(int, input().split())
l = sorted(map(int, input().split()))
x = n * 2
for i in range(k):
	x = min(x, n - (l[(i + 1) % k] - l[i]) % n)
print(x)


(k, n) = map(int, input().split())
a = [int(i) for i 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)


(K, N) = list(map(int, input().split()))
As = list(map(int, input().split()))
As += [As[0] + K]
maxDiff = 0
for i in range(N):
	d = As[i + 1] - As[i]
	if d > maxDiff:
		maxDiff = d
print(K - maxDiff)


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
A += [A[0] + K]
D = [abs(A[n + 1] - A[n]) for n in range(N)]
print(K - max(D))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
da = [-1] * n
da[n - 1] = k - a[n - 1] + a[0]
for i in range(n - 1):
	da[i] = a[i + 1] - a[i]
print(sum(da) - max(da))


(k, n) = map(int, input().split())
l = list(map(int, input().split()))
l = l + [l[0] + k]
ans = k
for i in range(n):
	ans = min(ans, k - (l[i + 1] - l[i]))
print(ans)


def lcm(a, b):
	return a * b // math.gcd(a, b)
MOD = 10 ** 9 + 7
(k, n) = list(map(int, input().split()))
A = list(map(int, input().split()))
m = 2 * 10 ** 5
M = [0] * n
dist = min(A[n - 1] - A[0], k - A[n - 1] + A[0])
for i in range(n - 1):
	dist = max(dist, A[i + 1] - A[i])
print(k - dist)


(k, n) = list(map(int, input().split()))
a = list(map(int, input().split()))
new_a = sorted(a)
num = len(new_a) - 1
s_a = []
b = k - new_a[num] + new_a[0]
s_a.append(b)
cun = 0
for i in new_a[1:]:
	s = i - new_a[cun]
	s_a.append(s)
	cun += 1
max_num = max(s_a)
print(sum(s_a) - max_num)


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
d = [(a[(i + 1) % n] - a[i]) % k for i in range(n)]
print(sum(d) - max(d))


((k, n), (*a,)) = [list(map(int, i.split())) for i in open(0)]
a.append(a[0] + k)
print(k - max((a[i + 1] - a[i] for i in range(n))))


(k, n) = map(int, input().split())
A = list(map(int, input().split()))
B = []
t = 0
for a in A:
	B.append(a - t)
	t = a
B[0] += k - t
print(k - max(B))


(K, N) = map(int, input().split())
l = list(map(int, input().split()))
L1 = [l[i + 1] - l[i] for i in range(N - 1)]
L1.append(K - l[N - 1] + l[0])
print(K - max(L1))


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


(K, N) = map(int, input().split())
A_s = list(map(int, input().split()))
MAX = max(list(map(lambda i: (A_s[(i + 1) % N] - A_s[i]) % K, range(N))))
print(K - MAX)


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


(K, N) = list(map(int, input().split()))
A_list = list(map(int, input().split()))
A_list.append(K + A_list[0])
dif_list = [0] * N
for i in range(N):
	dif_list[i] = A_list[i + 1] - A_list[i]
print(K - max(dif_list))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
m = k - a[n - 1] + a[0]
for i in range(n - 1):
	m = max(m, a[i + 1] - a[i])
x = k - m
print(x)


(K, N) = map(int, input().split())
A = [int(a) for a in input().split()]
A.append(A[0] + K)
b = []
max = 0
sum = 0
for i in range(N):
	t = A[i + 1] - A[i]
	sum += t
	if max < t:
		max = t
sum -= max
print(sum)


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
m = 0
for i in range(n - 1):
	if a[i + 1] - a[i] > m:
		m = a[i + 1] - a[i]
if k - a[n - 1] + a[0] > m:
	m = k - a[n - 1] + a[0]
print(k - m)


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
longest = k - a[-1] + a[0]
for i in range(len(a) - 1):
	longest = max(longest, a[i + 1] - a[i])
print(k - longest)


(k, n) = map(int, input().split())
a_list = list(map(int, input().split()))
longest = 0
for i in range(n):
	if i == n - 1:
		longest = max(longest, k - a_list[i] + a_list[0])
	else:
		distance = a_list[i + 1] - a_list[i]
		longest = max(longest, distance)
print(k - longest)


(K, N) = map(int, input().split())
A = [int(i) for i in input().split()]
A.append(A[0] + K)
max = 0
for i in range(N):
	if max <= A[i + 1] - A[i]:
		max = A[i + 1] - A[i]
print(K - max)


(K, N) = 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:])]))


import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
input = sys.stdin.readline

def RD():
	return input().rstrip()

def F():
	return float(input().rstrip())

def I():
	return int(input().rstrip())

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def LI():
	return list(map(int, input().split()))

def TI():
	return tuple(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def Init(H, W, num):
	return [[num for i in range(W)] for j in range(H)]

def main():
	(K, N) = MI()
	L = LI()
	res = L[-1] - L[0]
	max_num = L[-1]
	for i in range(1, N):
		temp = L[i]
		past = L[i - 1]
		past += K - temp
		res = min(res, past)
	print(res)

def __starting_point():
	main()
__starting_point()


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
dist = [A[0] + K - A[-1]] + [A[i] - A[i - 1] for i in range(1, N)]
print(K - max(dist))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
d = []
for i in range(n - 1):
	d.append(a[i + 1] - a[i])
d.append(k - a[n - 1] + a[0])
d.sort()
print(sum(d[:-1]))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
t = []
for (i, j) in zip(a, a[1:]):
	t.append(j - i)
t.append(k + a[0] - a[-1])
print(k - max(t))


(k, n) = map(int, input().split())
A = [int(i) for i in input().split()]
dif = [A[i + 1] - A[i] for i in range(n - 1)]
dif.append(k - A[-1] + A[0])
print(k - max(dif))


R = lambda : map(int, input().split())
(k, n) = R()
a = list(R())
print(k - max((y - x for (x, y) in zip(a, a[1:] + [a[0] + k]))))


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


(k, n, *aa) = map(int, open(0).read().split())
aa.append(k + aa[0])
print(k - max((a - b for (a, b) in zip(aa[1:], aa[:-1]))))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
ans = k
mx = k - a[-1] + a[0]
for i in range(n - 1):
	mx = max(mx, abs(a[i] - a[i + 1]))
print(ans - mx)


(k, n) = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * n
B[0] = k - A[n - 1] + A[0]
for i in range(1, n):
	B[i] = A[i] - A[i - 1]
print(k - max(B))


(A, B) = map(int, input().split())
f = list(map(int, input().split()))
kyori = []
for i in range(len(f) - 1):
	an = f[i + 1] - f[i]
	kyori.append(an)
an2 = A - f[-1] + f[0]
ans = max(max(kyori), an2)
print(A - ans)


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
bef = a[0]
max_diff = 0
for i in range(1, n):
	diff = abs(bef - a[i])
	max_diff = max(diff, max_diff)
	bef = a[i]
print(k - max(max_diff, k - abs(a[n - 1] - a[0])))


(k, n) = map(int, input().split())
L = list(map(int, input().split()))
L.append(k + L[0])
m = 0
for i in range(n):
	m = max(m, L[i + 1] - L[i])
print(k - m)


(K, N, *A) = map(int, open(0).read().split())
diff = A[0] + K - A[-1]
for i in range(1, N):
	diff = max(diff, A[i] - A[i - 1])
print(K - diff)


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
n = len(a) - 1
cnt = [a[n] - a[0]]
for i in range(n):
	cnt.append(k - (a[i + 1] - a[i]))
ans = min(cnt)
print(ans)


(k, n, *l) = map(int, open(0).read().split())
print(min(((l[i - 1] - l[i]) % k for i in range(n))))


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
ma = 0
for i in range(N - 1):
	ma = max(ma, A[i + 1] - A[i])
print(min(K - ma, A[N - 1] - A[0]))


(K, N) = list(map(int, input().split()))
A = list(map(int, input().split()))
a = 0
if A[0] == 0:
	a = K - A[N - 1]
else:
	a = min(A[N - 1] - A[0], K - A[N - 1] + A[0])
for i in range(N - 1):
	b = A[i + 1] - A[i]
	a = max(a, b)
ans = K - a
print(ans)


import math
import decimal

def i_input():
	return int(input())

def i_map():
	return map(int, input().split())

def i_list():
	return list(map(int, input().split()))

def i_row(N):
	return [int(input()) for _ in range(N)]

def i_row_list(N):
	return [list(map(int, input().split())) for _ in range(N)]
(k, n) = i_map()
aa = i_list()
dis = []
for i in range(n):
	if i == 0:
		dis.append(k - aa[-1] + aa[0])
	else:
		dis.append(aa[i] - aa[i - 1])
print(k - max(dis))


(K, N) = map(int, input().split())
A = [int(a) for a in input().split()]
D = [A[i + 1] - A[i] for i in range(N - 1)]
D.append(K + A[0] - A[N - 1])
print(K - max(D))


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
print(K - max((b - a for (a, b) in zip(A, A[1:] + [A[0] + K]))))


(K, N) = map(int, input().split())
Alst = list(map(int, input().split()))
zero = Alst[0] + K
M = 0
now = Alst[0]
for i in Alst:
	dis = i - now
	if dis > M:
		M = dis
	now = i
last = zero - now
if last > M:
	M = last
print(K - M)


f = lambda : [*map(int, input().split())]
(k, n) = f()
l = f()
l += [l[0] + k]
a = 0
for i in range(n):
	a = max(a, l[i + 1] - l[i])
print(k - a)


(K, N) = map(int, input().split(' '))
A_ls = list(map(int, input().split(' ')))
rst = -1
for i in range(N):
	l = A_ls[(i + 1) % N] - A_ls[i]
	if l < 0:
		l = K - A_ls[i] + A_ls[(i + 1) % N]
	if rst == -1:
		rst = l
	else:
		rst = max(rst, l)
print(K - rst)


(K, N) = map(int, input().split())
A = [int(x) for x in input().split()]
ans = A[0] + K - A[N - 1]
for i in range(N - 1):
	ans = max(ans, A[i + 1] - A[i])
print(K - ans)


f = lambda : map(int, input().split())
(k, n) = f()
l = list(f())
print(min(((l[i - 1] - l[i]) % k for i in range(n))))


(k, n) = map(int, input().split())
A = list(map(int, input().split()))
ans = []
for i in range(n):
	ans.append(A[-1] - A[i])
	A.append(k + A[i])
print(min(ans))


(k, n, *a) = map(int, open(0).read().split())
a += [a[0] + k]
d = [abs(a[i] - a[i + 1]) for i in range(n)]
print(k - max(d))


(k, n) = list(map(int, input().split()))
cnt = [0] * (n + 1)
cmb = 0
a = list(map(int, input().split()))
ans = 10 ** 6 + 1
for i in range(n):
	r_idx = (i + 1) % n
	r_ans = a[i] + (k - a[r_idx]) if a[i] < a[r_idx] else abs(a[r_idx] - a[i])
	l_idx = (i - 1 + n) % n
	l_ans = k - a[i] + a[l_idx] if a[i] > a[l_idx] else a[l_idx] - a[i]
	ans = min([ans, r_ans, l_ans])
print(ans)


(K, N, *A) = map(int, open(0).read().split())
A.append(K + A[0])
B = [b - a for (a, b) in zip(A, A[1:])]
print(sum(B) - max(B))


(K, N) = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = 10 ** 18
for i in range(N):
	if i == 0:
		clock_distance = A[N - 1] - A[i]
		reverse_distance = K - A[i + 1] + A[i]
	elif i == N - 1:
		clock_distance = K - A[i] + A[i - 1]
		reverse_distance = A[i] - A[0]
	else:
		clock_distance = K - A[i] + A[i + 1]
		reverse_distance = K - A[i + 1] + A[i]
	ans = min(clock_distance, reverse_distance, ans)
print(ans)


(t, n) = map(int, input().split())
x = list(map(int, input().split()))
x.insert(0, x[-1] - t)
dis = [x[i + 1] - x[i] for i in range(n)]
print(sum(dis) - max(dis))


(k, n, *A) = map(int, open(0).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)


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
ans = K - max(((A[(i + 1) % N] - A[i]) % K for i in range(N)))
print(ans)


(K, N) = list(map(int, input().split()))
A = list(map(int, input().split()))
B = []
for j in range(N - 1):
	B.append(A[j + 1] - A[j])
C = A[0] + K - A[N - 1]
B.append(C)
B.sort()
print(K - B[N - 1])


(K, N) = list(map(int, input().split()))
A = list(map(int, input().split()))
A = sorted(A)
L = []
ANS = 0
A_max = max(A)
for i in range(N - 1):
	L.append(abs(A[i + 1] - A[i]))
L.append(K + A[0] - A_max)
L = sorted(L)
L.pop(-1)
for i in range(len(L)):
	ANS = ANS + L[i]
print(ANS)


(K, n) = map(int, input().split())
a = list(map(int, input().split()))
a.append(K + a[0])
dif = 0
for i in range(n):
	dif = max(dif, a[i + 1] - a[i])
print(K - dif)


import sys
a = sys.stdin.buffer.read
(K, N, *A) = map(int, a().split())
A += [A[0] + K]
print(K - max((y - x for (x, y) in zip(A, A[1:]))))


import numpy as np
(k, n) = map(int, input().split())
a = list(map(int, input().split()))
dif = []
for i in range(len(a)):
	if i == 0:
		dif.append(k - a[-1] + a[0])
	else:
		dif.append(a[i] - a[i - 1])
dif = np.array(dif)
max_dif_idx = np.argmax(dif)
print(dif.sum() - dif[max_dif_idx])


(K, N) = list(map(int, input().split()))
A = list(map(int, input().split()))
dif = []
for (i, a) in enumerate(A[:len(A) - 1]):
	dif.append(A[i + 1] - a)
dif.append(K - A[len(A) - 1] + A[0])
print(K - max(dif))


(K, N) = list(map(int, input().split()))
dis = list(map(int, input().split()))
dif = []
for i in range(N - 1):
	dif.append(int(dis[i + 1] - dis[i]))
dif.append(int(K - dis[N - 1] + dis[0]))
print(K - max(dif))


(k, n) = list(map(int, input().split()))
a = list(map(int, input().split()))
a1 = sorted(a)
temp = list()
x = len(a) - 1
for i in range(x):
	temp.append(a1[i + 1] - a1[i])
temp.append(min(max(a) - min(a), k - max(a) + min(a)))
ans = k - max(temp)
print(ans)


(k, n) = map(int, input().split())
A = list(map(int, input().split()))
d = 0
for i in range(n - 1):
	d = max(d, A[i + 1] - A[i])
d1 = k - A[n - 1] + A[0]
d = max(d, d1)
print(k - d)


import numpy as np
(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = np.sort(a)
a = np.append(a, n + a[0])
a1 = np.append(0, a[:-1])
b = a - a1
b = b[1:]
print(np.sum(b) - np.max(b))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
b = [min(k - abs(a[-i] - a[-i - 1]), abs(a[-i] - a[-i - 1])) for i in range(n)]
print(k - max(b))


(k, n) = map(int, input().split())
(a, c) = ([*map(int, input().split())], [0] * n)
for i in range(n - 1):
	c[i] = a[i + 1] - a[i]
c[-1] = a[0] + k - a[-1]
print(k - max(c))


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


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.append(l[0] + n)
print(n - max((l[i + 1] - l[i] for i in range(m))))


(k, n) = map(int, input().split())
an = list(map(int, input().split()))
an.append(k + an[0])
max_length = 0
for i in range(n):
	max_length = max(max_length, an[i + 1] - an[i])
print(k - max_length)


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


(K, N) = list(map(int, input().split()))
A = list(map(int, input().split()))
A2 = [K + a for a in A]
A3 = A + A2
dist = [0] * N
for i in range(N):
	j = i + N - 1
	dist[i] = A3[j] - A[i]
print(min(dist))


(k, n) = map(int, input().split())
points = list(map(int, input().split()))
dist = []
for i in range(n):
	if i != n - 1:
		distance = points[i + 1] - points[i]
	else:
		distance = points[0] + k - points[i]
	dist.append(distance)
max = dist[0]
for j in range(1, len(dist), 1):
	if max < dist[j]:
		max = dist[j]
dist.remove(max)
ans = 0
for k in dist:
	ans += k
print(ans)


def i_input():
	return int(input())

def i_map():
	return map(int, input().split())

def i_list():
	return list(map(int, input().split()))

def i_row(N):
	return [int(input()) for _ in range(N)]

def i_row_list(N):
	return [list(map(int, input().split())) for _ in range(N)]
(k, n) = i_map()
aa = i_list()
dif = []
for i in range(n):
	if i == n - 1:
		dif.append(k - aa[-1] + aa[0])
	else:
		dif.append(aa[i + 1] - aa[i])
print(k - max(dif))


try:
	(K, N) = map(int, input().split())
	A = list(map(int, input().split()))
	li = []
	for i in range(N - 1):
		li.append(A[i + 1] - A[i])
	li.append(abs(A[0] + (K - A[-1])))
	print(sum(li) - max(li))
except:
	pass


(k, n) = map(int, input().split())
alst = list(map(int, input().split()))
alst.append(alst[0] + k)
minus = 0
for i in range(n):
	minus = max(minus, alst[i + 1] - alst[i])
print(k - minus)


(k, n) = map(int, input().split())
an = [int(num) for num in input().split()]
distance = []
for i in range(n - 1):
	distance.append(an[i + 1] - an[i])
distance.append(an[0] + (k - an[n - 1]))
distance.sort()
print(k - distance[n - 1])


(K, N) = list(map(int, input().split()))
A = [int(x) for x in input().split()]
mx = A[0] + K - A[-1]
for i in range(len(A) - 1):
	dis = A[i + 1] - A[i]
	if dis > mx:
		mx = dis
print(K - mx)


(l, n) = map(int, input().split())
a = input().split()
for i in range(n):
	a[i] = int(a[i])
min = l + a[0] - a[n - 1]
for i in range(n - 1):
	if min < a[i + 1] - a[i]:
		min = a[i + 1] - a[i]
print(l - min)


(K, N) = list(map(int, input().split()))
A = list(map(int, input().split()))
B = []
for i in range(len(A) - 1):
	B.append(A[i + 1] - A[i])
B.append(A[0] - A[N - 1] + K)
b_max = max(B)
b_max_index = B.index(max(B))
B.remove(b_max)
print(sum(B))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
l = []
t = 0
for i in a:
	l.append(i - t)
	t = i
l[0] += k - i
print(sum(l) - max(l))


(K, N) = map(int, input().split())
A = [int(i) for i in input().split()]
ma = K - A[-1] + A[0]
for i in range(N - 1):
	Z = A[i + 1] - A[i]
	ma = max(ma, Z)
print(K - ma)


(k, n) = map(int, input().split())
al = list(map(int, input().split()))
d = [a_ - a for (a, a_) in zip(al, al[1:])] + [k - al[-1] + al[0]]
print(sum(sorted(d)[:-1]))


(K, N) = map(int, input().split())
A_l = sorted(map(int, input().split()))
d_l = [K + A_l[0] - A_l[N - 1]]
for i in range(1, N):
	d_l.append(A_l[i] - A_l[i - 1])
print(K - max(d_l))


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


(k, n) = map(int, input().split())
l = list(map(int, input().split()))
m = 0
tmp = l[-1] - k
for i in l:
	m = max(m, i - tmp)
	tmp = i
print(k - m)


(k, n) = list(map(int, input().split()))
a = list(map(int, input().split()))
route = []
for i in range(n - 1):
	move = a[i + 1] - a[i]
	route.append(move)
route.append(k - a[-1] + a[0])
print(sum(route) - max(route))


(K, N) = map(int, input().split())
a = list(map(int, input().split()))
x = [a[0] - a[-1] + K]
for i in range(1, N):
	x.append(a[i] - a[i - 1])
print(K - max(x))


import numpy as np
(K, N) = map(int, input().split())
A = np.array(list(map(int, input().split())))
diff = np.append(A[1:] - A[:-1], K + A[0] - A[-1])
print(np.delete(diff, np.argmax(diff)).sum())


(K, n, *a) = map(int, open(0).read().split())
s = 0
for i in range(n):
	s = max(s, a[i] - a[i - 1])
print(K - max(s, a[0] + K - a[-1]))


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(N - 1):
	B.append(A[i + 1] - A[i])
B.append(K - A[N - 1] + A[0])
ans = K - max(B)
print(ans)


(K, N) = map(int, input().split())
(*A,) = sorted(map(int, input().split()))
print(K - max([*[A[i + 1] - A[i] for i in range(N - 1)], A[0] + (K - A[-1])]))


import sys
sys.setrecursionlimit(10 ** 8)
ini = lambda : int(sys.stdin.readline())
inl = lambda : [int(x) for x in sys.stdin.readline().split()]
ins = lambda : sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print('\x1b[33m', *a, '\x1b[0m', **dict(file=sys.stderr, **kw))

def solve():
	(k, n) = inl()
	A = inl()
	dmax = A[0] + (k - A[-1])
	for i in range(1, n):
		dmax = max(dmax, A[i] - A[i - 1])
	return k - dmax
print(solve())


(k, n, *A) = map(int, open(0).read().split())
B = [a1 - a0 for (a0, a1) in zip(A, A[1:])] + [k - A[-1] + A[0]]
print(sum(B) - max(B))


import numpy as np
(k, n) = map(int, input().split())
a_array = list(map(int, input().split()))
a_array.append(k + a_array[0])
a_diff = np.diff(a_array)
ans = np.sum(a_diff) - np.max(a_diff)
print(ans)


(k, _, *a) = map(int, open(0).read().split())
a.append(k + a[0])
b = [y - x for (x, y) in zip(a, a[1:])]
print(sum(b) - max(b))


(k, n, *a) = map(int, open(0).read().split())
a.sort()
print(k - max([i - j for (i, j) in zip(a[1:], a)] + [k - a[-1] + a[0]]))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
b = -a[0]
for i in range(1, n):
	b = min(b, k - a[n - 1] - a[i] + a[i - 1])
print(b + a[n - 1])


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
l = []
p = A[-1] - K
for a in A:
	l.append(a - p)
	p = a
print(sum(l) - max(l))


(K, N) = map(int, input().split())
As = list(map(int, input().split()))
As.append(K + As[0])
print(K - max((As[i + 1] - As[i] for i in range(N))))


(k, n) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
ans = k - l[n - 1] + l[0]
for i in range(n - 1):
	if l[i + 1] - l[i] >= ans:
		ans = l[i + 1] - l[i]
print(k - ans)


(k, n) = map(int, input().split())
(*l,) = map(int, input().split())
d = 0
for i in range(n - 1):
	d = max([d, l[i + 1] - l[i]])
d = max([d, l[0] + k - l[-1]])
print(k - d)


(k, n) = map(int, input().split())
l = list(map(int, input().split()))
v = [k - l[-1] + l[0]]
for i in range(n - 1):
	v.append(l[i + 1] - l[i])
v.sort()
print(k - v[-1])


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
root = []
ans = 0
for i in range(0, n - 1):
	x = a[i + 1] - a[i]
	root.append(x)
y = a[0] + k - a[n - 1]
root.append(y)
for i in root:
	ans += i
ans -= max(root)
print(ans)


(K, N) = map(int, input().split())
A = [int(i) for i in input().split()]
res = A[-1] - A[0]
for i in range(N - 1):
	res = min(res, K - (A[i + 1] - A[i]))
print(res)


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
e = a[1:] + [k + a[0]]
l = [abs(x - y) for (x, y) in zip(a, e)]
print(sum(l) - max(l))


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
nums = [0] * N
for i in range(N - 1):
	nums[i] = A[i + 1] - A[i]
nums[-1] = K + A[0] - A[-1]
print(sum(nums) - max(nums))
return


import numpy as np
(k, n) = map(int, input().split())
a = list(map(int, input().split()))
dist = [a[i + 1] - a[i] if i < n - 1 else k - a[i] + a[0] for i in range(n)]
max_index = np.argmax(dist)
cost = 0
curr_index = max_index
for _ in range(n - 1):
	if curr_index == 0:
		cost += a[curr_index] + k - a[curr_index - 1]
	else:
		cost += a[curr_index] - a[curr_index - 1]
	curr_index -= 1
print(cost)


def main():
	(k, n) = map(int, input().split())
	a = [int(v) for v in input().split()]
	distances = []
	for i in range(1, len(a)):
		distances.append(a[i] - a[i - 1])
	distances.append(k + a[0] - a[-1])
	maximum = max(distances)
	return k - maximum

def __starting_point():
	print(main())
__starting_point()


(k, n) = map(int, input().split())
(*a,) = map(int, input().split())
a += [i + k for i in a]
print(min((j - i for (i, j) in zip(a, a[n - 1:]))))


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
max_d = 0
for a in range(1, N):
	d = A[a] - A[a - 1]
	if d > max_d:
		max_d = d
last_d = K - A[-1] + A[0]
if last_d > max_d:
	max_d = last_d
print(K - max_d)


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

class Solution:

	def __init__(self, k, n, an):
		self.k = k
		self.n = n
		self.an = an

	@staticmethod
	def __append_first():
		an.append(k + an[0])
		new_an = an
		return new_an

	def answer(self):
		new_an = self.__append_first()
		max_length = 0
		for i in range(n):
			max_length = max(max_length, new_an[i + 1] - new_an[i])
		print(k - max_length)
conditions = Solution(k, n, an)
conditions.answer()


(K, N) = map(int, input().split())
lis = list(map(int, input().split()))
dt = [lis[i + 1] - lis[i] for i in range(N - 1)] + [lis[0] + (K - lis[-1])]
print(K - max(dt))


(K, N) = map(int, input().split())
A1 = list(map(int, input().split()))
D = [0] * N
A2 = [A1[i] + K for i in range(len(A1) - 1)]
A1 = A1 + A2
for i in range(N):
	D[i] = A1[i + N - 1] - A1[i]
print(min(D))


(K, N) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
print(min((K - (A[i] - A[i - 1]) % K for i in range(N))))