Problem:


Score : 300 points

Problem Statement

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 1

20 3
5 10 15

Sample Output 1

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.

Sample Input 2

20 3
0 5 15

Sample Output 2

10

If you start at the 2-nd house and go to the 1-st and 3-rd houses in this order, the total distance traveled will be 10.



Sample input:
20 3
5 10 15


Sample output:
10

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
l = list(map(int, input().split()))
d = []
for i in range(n):
  if i+1<n:
    d.append(abs(l[i+1]-l[i]))
  else:
    if 0 in l:
      d.append(abs(k - l[i]))
    else:
      d.append(abs(k - l[i] + l[0]))
print(sum(d)-max(d))

Submission status: Accepted

Solution code:
e = list(map(int,input().split()))
K = e[0]
N = e[1]
a = list(map(int,input().split()))
c = [a[i+1] - a[i] for i in range(N-1)]
f = a[0]+ K - a[N-1]
c.append(f)
d = max(c)
print(K - d)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def main():
    k,n=map(int,input().split())
    a=list(map(int,input().split()))
    resf=10**7
    z=0
    for i in a:
        if i==a[0]:
            res=min(a[-1]-a[0],k-(a[1]-a[0]))
        elif i==a[-1]:
            res=min(k-(a[-1]-a[-2]),a[-1]-a[0])
        else:
            if k-(a[z+1]-i)<=k-(i-a[z-1]):
                res=k-(a[z+1]-i)
            else:
                res=k-(i-a[z-1])
        if resf>=res:
            resf=res
        z+=1
    print(resf)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))

dists = [K-A[-1]+A[0]]

for i in range(1,N):
  tmp = A[i] - A[i-1]
  dists.append(tmp)

print(K-max(dists))

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(a[0] + k)
dis = [a1 - a0 for a0, a1 in zip(a, a[1:])]
print(k - max(dis))

Submission status: Accepted

Solution code:
import numpy as np
K, N = map(int, input().split())
A = np.array(list(map(int, input().split())))
diff = A[1:] - A[:-1]
diff = np.append(diff, K + A[0] - A[-1])
# print('diff', diff)
ans = diff.sum() - diff.max()
print(ans)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

dist=[None]*N
for i in range(N):
    if i==N-1:
        dist[i]=A[0]+K-A[i]
    else:
        dist[i]=A[i+1]-A[i]
#print(dist)
print(sum(dist)-max(dist))

Submission status: Accepted

Solution code:
# わからない
import numpy as np
k, n = map(int, input().split())
a = np.array(list(map(int, input().split())))
maxi = -1
for i in range(0, len(a)):
    if i == 0:
        tmp = max(abs((a[i] + k) - a[i - 1]), abs(a[i] - a[i + 1]))
    elif 0 < i < len(a) - 1:
        tmp = max(abs(a[i] - a[i - 1]), abs(a[i] - a[i + 1]))
    else:
        tmp = max(abs(a[i] - a[i-1]), abs(a[i] - (a[0] + k)))
    if maxi == -1:
        maxi = tmp
    else:
        maxi = max(maxi, tmp)
print(k - maxi)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

dis = (K - A[-1]) + A[0] 

for i in range(N-1):
    dis = max(dis, A[i+1] - A[i])
print(K - dis)

Submission status: Accepted

Solution code:
k,n=map(int,input().split())	
a=list(map(int,input().split()))
ans=a[-1]-a[0]
for i in range(n-1):
    t=k-(a[i+1]-a[i])
    if t<=ans:
        ans=t

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
K, N = map(int, input().split())
A = list(map(int, input().split()))
# print(K, N)
# print("A:", A)
A = A + [K + A[0]]
# print("A:", A)

lst = [A[i + 1] - A[i] for i in range(N)]
# print(lst)
print(K - max(lst))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
KN = input("").split()
A = input("").split()

K = int(KN[0])
N = int(KN[1])
A_0 = int(A[0])
A_N = int(A[N-1])
L = A_0

for j in range(N-1):
    A_i = int(A[j+1])
    A_m = int(A[j])
    if A_i - A_m > L:
        L = A_i - A_m

if L > K - A_N + A_0:
    print(K-L)
else:
    print(A_N - A_0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K, N=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))

Submission status: Accepted

Solution code:
K,N = map(int, input().split())
A =  [int(N) for N in input().split()]

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

B.append(int(A[0]+(K-A[N-1])))

B.sort()

Big = B[N-1]

print(K-Big)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    K, N = map(int, input().split(' '))
    A = list(map(int, input().split()))
    A.sort()
    A.append(A[0] + K)
    max_diff = A[0] + K - A[-1]
    for a, b in zip(A, A[1:]):
        if (b - a) > max_diff:
            max_diff = b - a
    print(K - max_diff)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
aa = list(map(int, input().split()))
 
mdiff = 0
for i in range(n):
    mdiff = max(mdiff, abs(k + aa[i] - aa[i - 1]) % k)
if n == 2:
    print(mdiff)
else:
    print(k - mdiff)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

diff = []
for i in range(len(distances)):
    if i == len(distances) - 1 :
        diff.append(k + distances[0] - distances[i])
    else:
        diff.append(distances[i + 1] - distances[i])
max_d = max(diff)
print(sum(diff) - max_d)

Submission status: Accepted

Solution code:
def main():
    k, n = map(int, input().split())
    houses = list(map(int, input().split()))

    distances = []
    for i in range(n):
        if i != n-1:
            distances.append(houses[i+1] - houses[i])
        else:
            distances.append(k-houses[-1] + houses[0])

    print(sum(distances) - max(distances))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k,n = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
ans = a[-1]-a[0]
for i in range(n-1):
  chk = a[i] + k-a[i+1]
  ans = min(ans,chk)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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:])]))

Submission status: Accepted

Solution code:
K, N = map(int, input().split())

house_list = list(map(int, input().split()))
#print(house_list)

dist_list = [K - house_list[-1] + house_list[0]]
#print(dist_list)

for n in range(1, N):
    dist_list.append(house_list[n] - house_list[n-1])
print(K - max(dist_list))

Submission status: Accepted

Solution code:
K,N = map(int, input().split())
AN = max = i = j = 0
c = []

A = [int(N) for N in input().split()]
while i+1 != N:
    c.append(A[i+1] - A[i])
    if c[i] > max:
        max = c[i]
    i = i+1

c.append(A[0] - 0 + K - A[N-1])

if A[0] - 0 + K - A[N-1] > max:
    max = A[0] - 0 + K - A[N-1]

while j != N:
    AN = AN + c[j]
    j = j + 1

AN = AN - max

print(AN)

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))
max_dist = 0
for i in range(n):
    dist = (a[(i + 1) % n] - a[i]) % k
    max_dist = max(max_dist, dist)
ans = k - max_dist
print(ans)

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))
 
max_dist = 0
for i in range(n):
    nxt = (i+1) % n
    distance = a[nxt] - a[i]
    if distance < 0:
        distance += k
    max_dist = max(max_dist, distance)
 
print(k-max_dist)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(a[0] + k)

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

Submission status: Accepted

Solution code:
import numpy as np
k,n=map(int,input().split())
l=list(map(int,input().split()))
l.append(k+l[0])
l=np.array(l)
p=np.diff(l)
print(k-np.max(p))

Submission status: Accepted

Solution code:
I = input().split()
K = int(I[0])
N = int(I[1])

I = input().split()

A = [ int(I[0]) ]
L = [ A[0] ]
for i in range(1,N):
  A.append( int(I[i]) )
  L.append( A[i] - A[i-1] )

L[0] = A[0]+(K-A[N-1])

L.sort()
print(K - L[N-1])

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

dis = (K-A[-1]) + A[0]
for i in range(len(A)-1):
    if A[i+1] - A[i] > dis:
        dis = A[i+1] - A[i]
print(K-dis)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def cal(a,b,k):
    return min(abs(a-b), k-abs(a-b))

def cal2(l):
    n = len(l)
    ans = 0
    for i in range(n-1):
        ans += l[i+1] - l[i]
    return ans
def main():
    k,n = map(int, input().split())
    As = list(map(int, input().split()))
    le = list()
    for i in range(n):
        if i == n-1:
            le.append(cal(As[i], As[0] , k) )
        else:
            le.append(As[i+1]- As[i])
    print(k-max(le))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k, n = tuple(map(int, input().split()))
a = list(map(int, input().split()))

a.append(k + a[0])

ans = [abs(a[(i + 1) % (n + 1)] - a[i]) for i in range(n)]
print(k - max(ans))

Submission status: Accepted

Solution code:
import numpy as np

K, N = [int(element) for element in input().split(" ")]
AList = np.array([int(element) for element in input().split(" ")])
distance = np.diff(AList)
start_end_distance = abs((K - AList[-1]) + AList[0])
distance = np.append(distance, start_end_distance)

print(K - np.max(distance))

Submission status: Accepted

Solution code:
K,N = map(int, input().split())
A = [int(N) for N in input().split()]
#print(A[0])
max1 = 0
max2 = 0
for i in range(0,N-1):
    max1 = A[i+1]-A[i]
    if max1>max2:
        max2=max1
if A[0]==0:
    lastlength = K-A[N-1]
    if lastlength >max2:
        max2=lastlength
else:
    lastlength = K-A[N-1]+A[0]
    if lastlength>max2:
        max2=lastlength
print(K-max2)

Submission status: Accepted

Solution code:
K,N = map(int, input().split(" "))
A = list(map(int, input().split(" ")))

X = 0
space = 0
idx = 0
A.append(A[0]+K)
for j in range(0,len(A)-1):
    X=0
    X = A[j+1] - A[j]
    if space < X:
        space = X
        idx = j
    
print(A[idx] + K - A[idx+1] )

Submission status: Accepted

Solution code:
import numpy as np

rawRounds = input()
rawDistances = input()

mizuumiRound = int(rawRounds.split()[0])
houseNumber = int(rawRounds.split()[1])
distances = [int(n) for n in rawDistances.split()]

sortedDistances = sorted(distances)

betweens = list(sortedDistances)
for i in range(len(betweens)-1) :
    betweens[i+1] -= sortedDistances[i]

betweens[0] = mizuumiRound - sortedDistances[len(sortedDistances)-1] + sortedDistances[0]

startPoint = betweens.index(max(betweens))

routeLen = sum(betweens) - betweens[startPoint]

print(routeLen)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

interval=[]
for i in range(N-1):
    interval+=[A[i+1]-A[i]]
    interval+=[A[0]+K-A[N-1]]
#     print(interval)
 
print(K-max(interval))

Submission status: Accepted

Solution code:
k, n = map(int, input().split())

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

Submission status: Accepted

Solution code:
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

k, n = I()
a = I()
ans = k
mx = 0
for i in range(n):
    mx = max(mx, (a[i] - a[i - 1]) % k)
print(ans - mx)

Submission status: Accepted

Solution code:
'''

2 2 4 4 4
11 12 13 14
21 22 23 24
1 2 3 4

'''

'''o=input().rstrip().split(' ')
x=int(o[0])
y=int(o[1])
a=int(o[2])
b=int(o[3])
c=int(o[4])
H=0;
R=input().rstrip().split(' ')
G=input().rstrip().split(' ')
ANY=input().rstrip().split(' ')
R.sort(key=int,reverse=True)
G.sort(key=int,reverse=True)
ANY.sort(key=int,reverse=True)
while(x>0):
    if int(R[0]) > int(ANY[0]):
        H+=int(R[0])
        del(R[0])
        x-=1;
    else:
        break;
while(y>0):
    if int(G[0]) > int(ANY[0]):
        H+=int(G[0])
        del(G[0])
        y-=1;
    else:
        break;
if(x>0 && y==0):
    for i in range(0,x):
        if i<len(ANY):
            H+=ANY[i];
        else:
            H+=int(R[0])
            del(R[0])
elif(y>0 && x==0):
    for i in range(0,y):
        if i<len(ANY):
            H+=ANY[i];
        else:
            H+=int(G[0])
            del(G[0])
else:
    FF=x+y;
    if FF<=len(ANY):
        for i in range(0,len(ANY)):
            H+=int(ANY[i])
    else:
        for i in range(0,len(ANY)):
            H+=int(ANY[i])
        XX=0;
        YY=0;
        for i in range(0,x):
            '''
            
            
'''

20 3
0 5 15

'''


o=input().rstrip().split(' ')
p=input().rstrip().split(' ')
l=[]
for i in range(1,len(p)):
    l.append(int(p[i]) - int(p[i-1]))
l.append(int(o[0])-int(p[len(p)-1])+int(p[0]))
q=[]
C=list(p)
A=list(C[0])
B=C[1:len(C)];
B.reverse();
C=A+B;
for i in range(1,len(C)):
    q.append(int(o[0]) - int(C[i]))
q.append(int(o[0]) - int(C[0]) + int(q[0]))
S=0
D=0
for i in range(0,len(l)):
    S+=int(l[i]);
    D+=int(q[i])
W=[]
minu = 10000000000000;
for i in range(0,len(l)):
    if i==0:
        F=S-int(l[len(l)-1])
        minu = min(minu,F)
    else:
        F=S-int(l[i-1])
        minu = min(minu,F);
for i in range(0,len(q)):
    if i==0:
        F=D-int(q[len(q)-1])
        minu = min(minu,F)
    else:
        F=D-int(q[i-1])
        minu = min(minu,F);
print(minu)

Submission status: Accepted

Solution code:
(n,m)=map(int,input().split())
a=input().split()
a=list(map(int,a))
l=[]
k=0
a=sorted(a)
for i in range(m-1):
    d=abs(a[i]-a[i+1])
    k=k+d
    l.append(d)
# k=k-d
c=n-k
l.append(c)
l=sorted(l)
l1=sum(l)
print(l1-l[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K, N = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

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

print(K - max(sum))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,N = map(int,input().split())

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
K, N = map(int, input().split())
A = list(map(int, input().split()))
A += [A[0] + K]
max_gap = max(y - x for x, y in zip(A, A[1:]))
print(K - max_gap)

Submission status: Accepted

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

print(k-max(sum))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	K,N = inputMap()
	A = inputList()

	toto = 0
	tmp = 0
	for j,vol in enumerate(A):
		if j == 0:
			tmp = vol
			continue
		toto += vol - tmp
		tmp = vol

	ans = toto
	toto = toto + (K - A[-1]) + A[0]

	A.append(K - A[-1] + A[0])

	for j,vol in enumerate(A):
		if j == 0:
			continue

		tmpans = toto - (vol - A[j-1])

		if ans > tmpans:
			ans = tmpans

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
k,n=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort() ; maxx=0
for i in range(len(a)-1):
    if a[i+1]-a[i]>maxx: maxx=a[i+1]-a[i]
if k+a[0]-a[-1]>maxx: maxx=k+a[0]-a[-1]
print(k-maxx)

Submission status: Accepted

Solution code:
import numpy as np

import sys

readline = sys.stdin.buffer.readline

K, N = map(int, readline().split())
A = list(map(int, readline().split()))
A.append(K + A[0])

D = np.diff(A)

print(int(K) - np.max(D))

Submission status: Accepted

Solution code:
# 初期入力
K,N = (int(x) for x in input().split(" "))
A = [0]
for i in input().split():
    if i !="0":
        A.append( int(i) )

# 1軒ずつ距離のリスト
x =[A[i+1] - A[i] for i,v in enumerate(A[:-1]) ]
if N == len(A):
    x.append(K -A[-1])
else:
    x.append(K - A[-1] +A[1])

#　求めるのは　K　－　max(隣と離れた家の距離)
kyori_min = K - max(x)
print(kyori_min)

Submission status: Accepted

Solution code:
k, n  = [int(x) for x in input().split()]
a_i  = [int(x) for x in input().split()]
diff_a_i = [a_i[i] - a_i[i-1] for i in range(n)]
diff_a_i[0] += k
diff_a_i.pop(diff_a_i.index(max(diff_a_i)))
print(sum(diff_a_i))

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
l = list(map(int, input().split()))
f = b - 1
g = b - 2
c = int(l[-1])
d = int(l[0])
v = list([1]*b)
for i in range (f):
  	v[i] = l[i+1]-l[i]
v[f] = a + l[0] - l[-1]
if	max(v) == v[f]:
	print(l[-1]-l[0])
else:
	print(a-max(v))

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = [int(e) for e in input().split()]

ans = 0
S = [(A[i + 1] - A[i]) for i in range(N - 1)]
S.append((K - A[N - 1]) + A[0])
S.sort
m = sorted(S)
for n in range(N - 1):
    ans += m[n]
print(ans)

Submission status: Accepted

Solution code:
#C

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

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

d = []
#d[]は各家の距離
for i in range(n-1):
    d.append(a[i+1] - a[i])

d.append(k - a[n-1] + a[0])

print(k - max(d))

Submission status: Accepted

Solution code:
k,n = input().split()

k,n = int(k), int(n)
lt = [int(x) for x in input().split()]
lt2 = lt.copy()
lt3 = lt2 + [i+k for i in lt]

mini = 1000000000000000

i=0
while i+n-1 < len(lt3):
    mini = min(mini, lt3[i+n-1] - lt3[i])
    i+=1
print(mini)

Submission status: Accepted

Solution code:
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])
print(k-max(b))

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = [int(x) for x in input().split()]
S = A[0]
A.insert(0,0)

def chmax(a,b):
    if a < b:
        return b,True
    else:
        return a,False

m = 0
r = 0
for i in range(1,N+1):
    # print("----")
    # print(i,"/",A[i-1],A[i])
    if i==N:
        # print("@", A[i-1], (K+S)-A[i])
        # print("¥", (K+S)-A[i])
        r = r+(K+S)-A[i]
        A[i],j = chmax(A[i-1], (K+S)-A[i])
        m = i if j else m
    else:
        # print(A[i-1], A[i+1]-A[i])
        r = A[i+1]-A[i]+r
        A[i],j = chmax(A[i-1], A[i+1]-A[i])
        m = i if j else m
    # print(A[i])


# print(m)
print(r-A[m])

Submission status: Accepted

Solution code:
def main():
    k, n = list(map(int,input().strip().split()))
    a = list(map(int,input().strip().split()))

    point_start = 0
    point_end = 0
    max_dist = 0
    tmp_dist = 0

    for i in range(len(a)-1):
        tmp_dist = max(max_dist, a[i+1]-a[i])
        if(tmp_dist!=max_dist):
            point_start = i+1
            max_dist = tmp_dist

    tmp_dist = max(max_dist, (k-a[n-1])+a[0])
    if(tmp_dist!=max_dist):
        point_start = 0
        max_dist = tmp_dist


    dist = 0

    for i in range(len(a)-1):
        if(point_start!=(n-1)):
            dist = dist + (a[point_start+1]-a[point_start])
            point_start = point_start + 1
        else:
            dist = dist + ((k-a[point_start])+a[0])
            point_start = 0

    print(dist)

main()

Submission status: Accepted

Solution code:
K,N = map(int,input().split())
A = list(map(int,input().split()))
ans = []

for i in range(N-1):
  now = i
  pre = now-1
  post = now +1
  #nowとpreの距離を求める
  if now == 0:
    preDic = (K-A[N-1])+A[now]
  else:
    preDic = A[now]-A[pre]
  postDic = A[post]-A[now]  
  if preDic >= postDic:#時計回りに、i-1の位置まで進む
    ans.append(K-preDic)
  else:
    ans.append(K-postDic)
  
print(min(ans))

Submission status: Accepted

Solution code:
K,N = map(int,input().split())
list_A = list(map(int,input().split()))

list_A.sort()

list_dis = list(range(N))
min = 1000
dis = 0


for i in range(N):
    if i == N-1:
         list_dis[i] = K - list_A[i] + list_A[0]
    else:
         list_dis[i] = list_A[i+1] - list_A[i]


list_dis.sort()
del list_dis[N-1]
print(sum(list_dis))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int,input().split()))
B = []

for i in range(N):
    if i == 0:
        B.append(A[N-1] - A[0])
        B.append(A[0] + (K - A[1]))
    elif i == (N - 1):
        B.append(A[N-1] - A[0])
        B.append((K - A[N-1]) + A[N-2])
    else:
        B.append((K - A[i]) + A[i-1])
        B.append(A[i] + (K - A[i+1]))

print(min(B))

Submission status: Accepted

Solution code:
import numpy as np

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

dist = []
dist.append(a[1]-a[0])

for num in range(1, len(a)):
  if num == len(a) - 1:
    dist.append(k-a[num]+a[0])
  else:
    dist.append(a[num+1]-a[num])
#print(dist)
dist = np.array(dist)

#min_index = np.where(dist == dist.min())[0]
s = np.sum(dist)
result = []
for start_index in range(0, len(dist)):
  if start_index == 0:
    result.append(s - dist[len(dist)-1])
    result.append(s - dist[start_index+1])
  elif start_index == len(dist)-1:
    result.append(s - dist[start_index-1])
    result.append(s - dist[0])
  else:
    result.append(s - dist[start_index-1])
    result.append(s - dist[start_index+1])
print(min(result))

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

ans_root = K
for i in range(N):
    if i==0:
        root = A[N-1] - A[0]
    else:
        root = A[i-1]+K - A[i]
    if ans_root > root:
        ans_root = root
print(ans_root)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k,n=map(int,input().split())

List=[int(i) for i in input().split()]
a=[]
b=len(List)
c=[]
for i in range(b):
    if i ==0:
        c.append(List[0]+(k-List[-1]))
    else:
        c.append(abs(List[i]-List[i-1]))
       
print(k-(max(c)))

Submission status: Accepted

Solution code:
K,N = map(int, input().split())
l = list(map(int,input().split()))


ans_list = []
flag = 0
num = 0
ans = 999999999999999
    
for i in range(N):
    if(l[i] == 0):
        flag =True
if(flag == True):
    
    for i in range(1,N):
          ans_list.append(l[i] - l[i-1])
    ans_list.append(K - l[N-1])
    
    for i in range(N):
        num = K - ans_list[i]
        ans = min(ans, num)
    print(ans)
    
else: 
    for i in range(1,N):
        ans_list.append(l[i] - l[i-1])
    ans_list.append(K-l[N-1] + l[0])
    max_length = max(ans_list)
    ans = K-max_length
    print(ans)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

lenmax = 0
for i in range(N-1):
    a = A[i+1] - A[i]
    #print(a)
    if a > lenmax:
        lenmax = a

#print(A[len(A)-1],A[0])
if K - (A[len(A)-1] - A[0]) > lenmax:
    lenmax = K - (A[len(A)-1] - A[0])

print(K-lenmax)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A =list(map(int, input().split()))

KK = int(K)


def smaler(x, y):
  if x < y:
    return x
  else:
    return y

def lager(x, y):
  if x > y:
    return x
  else:
    return y

 

def span(A, i):
  if i == 1:
    return K - A[len(A) - 1] + A[0]
  elif i != 1:
    return A[i] - A[i - 1]
    
m = 0
for i in range(0, len(A)):
  m = lager(m, span(A, i))

  
print(K - m)

Submission status: Accepted

Solution code:
s1 = str(input())
s = s1.split(' ')
k = int(s[0])
n = int(s[1])
l=[]

ls = str(input())
l = ls.split(' ')
l1 = [int(x) for x in l]

def dist(a,b,k):
    if(b>a):
        return (k-b)+a
    else:
        return a-b

l4=[]
for i in range(len(l1)):
    l4.append(k - dist(l1[i],l1[i-1],k))
        
    
print(min(l4))

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
a = list(map(int, input().split()))

m = 0
p = 0
for n in range(0, N):
    if (n == N - 1):
        if (K - a[n] + a[0] >= m):
            m = K - a[n] + a[0]
            p = n
    elif ((a[n + 1] - a[n]) >= m):
        m = a[n + 1] - a[n]
        p = n

if (p == N - 1):
    print(a[p] - a[0])
else:
    print(K - a[p + 1] + a[p])