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:
lake_circumference, house_count = map(int, input().split())
locations = list(map(int, input().split()))
min_distance = 10e6
for i in range(house_count):
    if i == 0:
        distance = locations[house_count-1] - locations[0]
    else:
        distance = lake_circumference + locations[i-1] - locations[i]
    if distance < min_distance:
        min_distance = distance
print(min_distance)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

K,N = map(int, input().split())
An = list(map(int, input().split()))
arr = np.array(An)
arr = np.diff(arr)
ans = list(arr)
ans.append(K-An[-1]+An[0])
# print(ans)
ans.remove(max(ans))
print(sum(ans))

Submission status: Accepted

Solution code:
import heapq

k, n = map(int, input().split())
a = [int(x) for x in input().split()]
qa = []
heapq.heapify(qa)

for x in range(len(a) - 1):
    heapq.heappush(qa, abs(a[x] - a[x + 1]))
heapq.heappush(qa, k - a[-1] + a[0])

dis = 0
for x in range(len(qa) - 1):
    dis += heapq.heappop(qa)

print(dis)

Submission status: Accepted

Solution code:
# 1行目の入力を空白で分割された数値として扱う
K, N = map(int, input().split())
# 2行目の入力を数値のリストとして扱う
A = list(map(int, input().split()))

# 答えの準備
ans = 0
max = 0

# 距離の取得
for i in range(0, N -1):
    d = A[i+1] - A[i]
    ans += d
    if d > max:
        max = d

# 一周した最後
dl = K - A[N - 1]
if dl + A[0] < max:
    ans = ans - max + dl + A[0]

# 出力
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

tokei = []

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,n=map(int,input().split())
d=[0]*n
b=[int(ss) for ss in input().split()]
#print(b)
for ii in range(n-1):
  d[ii+1]=b[ii+1]-b[ii]
#  b[ii]=(2*b[ii]+a)%(2*a)
#  print(b[ii])
d[0]=a-b[n-1]+b[0]
d=sorted(d)
#print(d)
print(a-max(d))

Submission status: Accepted

Solution code:
a = []
a = input().split()
K = int(a[0])
N = int(a[1])
#print('K=', K, 'N=', N)
A = []
A = input().split()
A = [int(i) for i in A]
#print('A=', A)

l = []

for i in range(len(A)-1):
  l.append(A[i+1] - A[i])
l.append(K - A[len(A)-1] + A[0])

#print('l=', l)

M = max(l)

#print('M=', M)

print(K - M)

Submission status: Accepted

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

dif =[]

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

for i in range(1,n):
    dif.append(a[i]-a[i-1])

dif.sort()
ans = 0
for i in range(n-1):
    ans += dif[i]

print(ans)

Submission status: Accepted

Solution code:
K, N = [int(x) for x in input().split()]
list = [0]*N
list = [int(x) for x in input().split()]
list.append(K+list[0])

a = 0
for i in range(N):
    if a < (list[i+1] - list[i]):
        a = list[i+1] - list[i]
        b = i

print(K-a)

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = [int(x) for x in input().split()]

diff = [a[i + 1] - a[i] for i in range(n - 1)] + [k - a[-1] + a[0]]
ans = sum(diff) - max(diff)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

a = list(map(int, input().split()))
a = sorted(a)
max_ = max(a)
min_ = min(a)
a_ = deepcopy(a)
ans = 100000000000
for index in range(len(a)):
    # temp = max(a) - min(a)
    # print(max_,min_)
    temp = max_ - min_
    max_ = min_ + k
    if index != len(a)-1:
        min_ = a[index+1]
    a[index] = a[index] + k
    # print(temp)
    if ans > temp:
        ans = temp

max_ = max(a_)
min_ = min(a_)

for index in reversed(range(len(a))):
    # print(a_, temp, max(a_), min(a_))
    # temp = (max(a_) - min(a_))
    # print(max_,min_)
    temp = max_-min_
    min_ = max_ -k
    if index != 0:
        max_ = a_[index-1]
    # print(temp)
    # a_[index] -= k
    if ans > temp:
        ans = temp

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

K,N=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
x=np.array(A[1:])
y=np.array(A[:-1])
B=x-y
C=B.tolist()
C.append(K+A[0]-A[N-1])
print(K-int(max(C)))

Submission status: Accepted

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

result = [K - abs(A[-1] - A[0])]
for i in range(N-1):
    diff = abs(A[i] - A[i+1])
    result.append(diff)

result.sort()
print(sum(result[:-1]))

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):
    ans = min(ans, K-(A[i]-A[i-1]))
    
print(ans)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
AA = list(map(int,input().split()))
 
KK = [False]*K
for a in AA:
  KK[a] = True
 
dist = 0
dist_max = 0
for i in range(2*K):
  if KK[int(i%K)] == 1:
    dist = 1
  else:
    dist += 1
  if dist > dist_max:
    dist_max = dist
print(K-dist_max)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

N,M=(int(x) for x in input().split())
A=list(map(int, input().split()))
A=np.array(A)
B=A[1:]-A[:-1]
b=max(B)
c=A[-1]-A[0]
if c > N/2:
    d=int(N-c)
else:
    d=c
e=max(b,d)
f=N-e

print(f)

Submission status: Accepted

Solution code:
import heapq

K, N = map(int, input().split())

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


dis = [-abs(A[i + 1] - A[i]) for i in range(N - 1)] + [-abs(abs(A[0]) + abs(K - A[N - 1]))]


heapq.heapify(dis)

heapq.heappop(dis)

print(-sum(dis))

Submission status: Accepted

Solution code:
a = input().split()
b = input().split()

K=int(a[0])
N=int(a[1])

#print(K, N)

b = [int(s) for s in b]

c=0
d=[]
for i in b:
  #print(i-c)
  d.append(i-c)
  c=i
d[0]=d[0]+K-b[N-1]
#print(d)
print(K-max(d))

Submission status: Accepted

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

max = K - A[-1] + A[0]
B.append(max)
ind = 0
for i in range(1, N):
	_max = A[i] - A[i-1]
	B.append(_max)
	if _max < 0:
		_max = K + _max
	if _max > max:
		max = _max
		ind = i
dis1 = 0

for i in range(1, N):
	if i + ind >= N:
		dis1 += B[(i + ind) - N]
	else:
		dis1 += B[(i + ind)]
        
print(dis1)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools

from collections import deque 
from functools import reduce

# input = sys.stdin.readline

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

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

a_np = np.array(a)
a_np = a_np.flatten()
a_np = np.hstack((a_np, k+a_np[0]))
a_sa = abs(a_np[:-1] - a_np[1:])
print(a_sa.sum() - a_sa.max())

Submission status: Accepted

Solution code:
from math import ceil,sqrt
def main():
    
    # for _ in range(ii()):
    
    # t=int(input())
    k,n=map(int,input().split())
    a=list(map(int,input().split()))
    b=[0]*n
    for i in range(n):
        if(i==0):
            b[i]=(a[n-1]-a[i])
        else:
            b[i]=(a[n-1]-a[i])+(k-a[n-1])+a[i-1]
    a1=[(k-i) for i in a]
    a1.reverse()
    b1=[0]*n
    for i in range(n):
        if(i==0):
            b1[i]=(a1[n-1]-a1[i])
        else:
            b1[i]=(a1[n-1]-a1[i])+(k-a1[n-1])+a1[i-1]
    b1.reverse()
    ans=1e9+7
    # print(b,b1)
    for i in range(n):
        ans=min(ans,min(b[i],b1[i]))
    print(int(ans))
    
    
    
    
    
    
    
    
    
    




    
if __name__ =="__main__":
    main()

Submission status: Accepted

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


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

L = 0

for i in range(n-1):
  M = A[i+1] - A[i]
  if M > L:
    L = M
      
M = (k-A[n-1]) + A[0]
if M > L:
  L = M
  
print(k-L)

Submission status: Accepted

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

y=[sum(b)]
for i in range(len(b)):
    y.append(k-b[i])
print(min(y))

Submission status: Accepted

Solution code:
import math
K,N=map(int,input().split())
A=list(map(int,input().split()))
A.append(A[0]+K)
maxi=0
max=0
dis=0
for i in range(len(A)-1):
    if A[i+1]-A[i]>max:
        max=A[i+1]-A[i]
        maxi=i
for i in range(0,maxi):
    dis+=A[i+1]-A[i]
for i in range(maxi+1,len(A)-1):
    dis+=A[i+1]-A[i]
print(dis)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
lis = []
for i in map(int, input().split()):
  lis.append(i)
  
max = k + lis[0] - lis[n-1]
for i in range(n-1):
  j = lis[i+1] - lis[i]
  if j > max:
    max = j

print(k-max)

Submission status: Accepted

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

for i in range(N-1):
  if i == 0:
    ans = min(ans,K - (A[i+1]-A[i]),A[-1]-A[i])
  else:
    ans = min(ans,K - (A[i+1]-A[i]),K - (A[i]-A[i-1]))

print(ans)

Submission status: Accepted

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

ans = A[N - 1] - A[0]
now = ans
for i in range(1, N):
  prior = A[i] - A[i - 1]
  if i == 1:
    #print(A[0], A[N - 1])
    next_ = A[0] + K - A[N - 1]
  else:
    next_ = A[i-1 ] - A[i -2] 
  
  now = now - prior + next_
  #print(i,ans, now, prior, next_)
  if ans > now:
    ans = now
print(ans)

Submission status: Accepted

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

tmp=[]
for i in range(N):
    if(i!=N-1):
        tmp.append(li[i+1]-li[i])
    else:
        tmp.append(li[0]+K-li[i])

id =tmp.index(max(tmp))
if(id<N-1):
    print(li[id]+K-li[id+1])
else:
    print(li[id]-li[0])

Submission status: Accepted

Solution code:
k,n=map(int,input().split())
a=[int(i) for i in input().split()]

distances=[]
for i in range(len(a)-1):
  distances.append(a[i+1]-a[i])

distances.append(k-a[len(a)-1]+a[0])

m=max(distances)

print(k-m)

Submission status: Accepted

Solution code:
K,N = map(int,input().split())
li = list(map(int,input().split()))
kyori = 0
for i in range(1,len(li)):
    if li[i] - li[i-1] > kyori:
        kyori = li[i] - li[i-1]
syokiti = li[0]+K-li[N-1]         
if syokiti < kyori:
    print(K - kyori)
else:
    print(K-syokiti)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
K,N = map(int, input().split())
houses = list(map(int, input().split()))
M = N - 1
lis = []
a = 0
while M > 0:
    lis.append(houses[a+1] - houses[a])
    M -= 1
    a += 1
lis.append(K - houses[N-1] + houses[0])
hou = sorted(lis, reverse = True)
del hou[0]
print(sum(hou))

Submission status: Accepted

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

X = list()
for i in range(n-1):
    x = A[i+1]-A[i]
    X.append(x)

y = k-A[n-1]+ A[0]

X.append(y)

m = max(X)

print(k-m)

Submission status: Accepted

Solution code:
k,n = list(map(int,input().split()))
a = list(map(int,input().split()))
mn = k+1
for i in range(n):
    nxt= (i+1)%n;
    prv= (i-1+n)%n;
    if a[i]<a[nxt]:
        diff1= k- (a[nxt]-a[i])
    else:
        diff1= a[i]-a[nxt]
    if a[i]>a[prv]:
        diff2=k-(a[i]-a[prv])
    else:
        diff2=a[prv]-a[i]
    mn=min(diff1,mn)
    mn=min(diff2,mn)
print(mn)

Submission status: Accepted

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

a = A[1] - A[0]

for i in range(1,N):
    b = A[i] - A[i-1]
    c = max(a,b)
    a = c

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

e = max(c,d)

print(K-e)

Submission status: Accepted

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

"""
5 - 0 #A1 - 0 i = 0
10 - 5#A2 -A1 i = 1
15 - 10#      i = 2
20 - 10  #K-A3 i = 3
"""
L = []
for i in range(N):
    if i == 0:
        continue
    else:
        L.append(A[i] - A[i - 1])
        
L.append(A[0] + K - A[N-1])

L = sorted(L, reverse=True)
del L[0]
print(sum(L))

Submission status: Accepted

Solution code:
input_first = input()
input_second = input()

split_input_first = input_first.split()
split_input_second = input_second.split()

k = int(split_input_first[0])
n = int(split_input_first[1])

distance_list = []
for i in range(n):
    if i == n - 1:
        distance_list.append(k + int(split_input_second[0]) - int(split_input_second[n-1]))
    else:
        distance_list.append(int(split_input_second[i+1]) - int(split_input_second[i]))
distance_list = sorted(distance_list)

result = 0
for i in range(n):
    if i == n - 1:
        break
    else:
        result += distance_list[i]
print(result)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
lis=list(map(int,input().split()))
li=[lis[i+1]-lis[i] for i in range(m-1)]
li.append(n-lis[-1]+lis[0])
print(sum(li)-max(li))

Submission status: Accepted

Solution code:
import numpy as np

K, N = map(int, input().split())
A = [int(x) for x in input().split()]
A.append(K+A[0])

diff_A = []
for i in range(N):
    diff_A.append(A[i+1] - A[i])
diff_max = max(diff_A)
print(K - diff_max)

Submission status: Accepted

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

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

table =[-1] * len(a)

for i in range(len(a)):
    if i < len(a) - 1:
        table[i] = a[i+1] - a[i]
    else:
        table[i] = a[0] + k - a[len(a)-1]
table.remove(max(table))

print(sum(table))

Submission status: Accepted

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

    d = []
    n = len(A)
    for i, a in enumerate(A):
        if i == 0:
            d.append(min(A[0] + K - A[1], A[n-1] - A[0]))
        elif i == n-1:
            d.append(min(A[n-1]-A[0], K-A[n-1]+A[N-2]))
        else:
            d.append(min(K-A[i]+A[i-1], A[i]+K-A[i+1]))

    print(min(d))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k, n, *A = map(int, open(0).read().split())

dist = A[0] + (k - A[-1])
maxdist = dist
start = 0

for i in range(n - 1):
    if maxdist < A[i + 1] - A[i]:
        start = i + 1
        maxdist = A[i + 1] - A[i]

if start == 0:
    print(A[-1] - A[0])
else:
    print(A[-1] - A[start] + dist + (A[start - 1] - A[0]))

Submission status: Accepted

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

def distance(a1, a2):
  return abs(a1 - a2)

sum, max = 0, 0
for i in range(N):
  if (i + 1) < N:
    d = distance(An[i], An[i+1])
    sum += d
    if(d > max):
      max = d
  else:
    d = distance(An[i], K) + distance(0, An[0])
    sum += d
    if(d > max):
      max = d

print(sum - max)

Submission status: Accepted

Solution code:
line = input().rstrip().split(' ')
k = int(line[0])
n = int(line[1])

line = input().rstrip().split(' ')
a = [0] * n
for i in range(n):
    a[i] = int(line[i])

ans = 1000000
for i in range(n):
    if i - 1 > -1:
        tmp1 = k - a[i] + a[i - 1]
    else:
        tmp1 = a[n - 1] - a[i]

    if i < n - 1:
        tmp2 = k - a[i + 1] + a[i]
    else:
        tmp2 = a[i] - a[0] 

    ans = min(ans, tmp1, tmp2)

print(ans)

Submission status: Accepted

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

dmax = 0
for i in range(N-1):
    d = A[i+1] - A[i]
    if d > dmax:
        dmax = d
if A[N-1] - A[0] < A[0] + (K - A[N-1]):
    d = A[N-1] - A[0]
    if d > dmax:
        dmax = d
    ans = dmax
else:
    d = A[0] + (K - A[N-1])
    if d > dmax:
        dmax = d
    ans = K - dmax

print(ans)

Submission status: Accepted

Solution code:
import math




perimeter,N = map(int,input().split())
data = list(map(int,input().split()))


biggest_gap = perimeter-(data[-1]-data[0])

for i in range(1,len(data)):
    biggest_gap = max(biggest_gap,data[i]-data[i-1])

shortest_path = perimeter-biggest_gap

print(shortest_path)

Submission status: Accepted

Solution code:
k, n = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.append(k + A[0])

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

print(k - MaxD)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

ans=0
if max(a)<=(k/2.0) or min(a)>=(k/2.0):
  for i in range(n-1):
    ans+=abs(a[i+1]-a[i])
else:
  max_=0
  for i in range(n-1):
    max_=max(max_,abs(a[i+1]-a[i]))
  max_=max(max_,abs(a[0]-(a[n-1]-k)))
  ans=k-max_
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

k,n = inpl()
a = inpl()
b = []
for i in range(1,n):
    b.append(abs(a[i] - a[i-1]))
b.append(k-a[-1] + a[0])
b.sort()
print(sum(b) - b[-1])

Submission status: Accepted

Solution code:


############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
k,n = invr()
nums = inlt()
ans = min(nums[-1] - nums[0],k - (nums[1] - nums[0]))
for i in range(1,n - 1):
    
    result = min(k - (nums[i] - nums[i - 1]), \
             k - abs(nums[i + 1] - nums[i]))
    #print(i,result)
    if result < ans:
        ans = result

ans = min(ans,k - (nums[-1] - nums[-2]))
print(ans)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int,input().split()))
for i in range(N):
  A.append(A[i]+K)
d = [0]*(N)
max_d, max_i = 0, -1
for i in range(N):
  d[i] = A[i+1] - A[i]
  if d[i] > max_d:
    max_d = d[i]
    max_i = i + 1
ans = 0
for i in range(N-1):
  ans += A[i+max_i+1] - A[i+max_i]
print(ans)

Submission status: Accepted

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

max = K - A[N-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())
s = list(map(int,input().split()))
a=[]
for num in range(n-1):

    p= s[num+1]-s[num]
    a.append(p)
b = s[0]+(k-s[-1])
a.append(b)
x = k-max(a)
print(x)

Submission status: Accepted

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

    pos = [-(K - a) for a in A] + A[:]
    diff = [abs(pos[i + 1] - pos[i]) for i in range(len(pos) - 1)]
    ans = sum(diff[:N - 1])
    tmp = ans

    left, right = 0, N - 1
    while right != len(diff):
        tmp -= diff[left]
        tmp += diff[right]
        ans = min(ans, tmp)
        left += 1
        right += 1
    return ans

print(c_traveling_salesman_around_lake())

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))
d = K - A[-1]
d = max(d, A[0] + (K - A[-1]))

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

Submission status: Accepted

Solution code:
k, n = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [min(a[i+1]-a[i], k-(a[i+1]-a[i])) for i in range(len(a)-1)]
b.append(min(a[len(a)-1] - a[0], k-(a[len(a)-1] - a[0])))
print(sum(b)-max(b))

Submission status: Accepted

Solution code:
# 各条件の入力
k, n = map(int, input().split())
a_iterator = map(int, input().split())
a = list(a_iterator)

# 判定
diff_list = [(a[i+1] - a[i]) for i in range(n-1)]

ans1 = max(a) - min(a)
ans2 = k - max(diff_list)

ans = min(ans1, ans2)

# 答えの出力
print(ans)

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
max_diff = k - a[n-1] + a[0]
for idx in range(len(a)-1):
  diff = a[idx+1] - a[idx]
  if max_diff < diff:
    max_diff = diff
max_diff = max_diff
ans = k - max_diff
print(ans)

Submission status: Accepted

Solution code:
# Problem C - Traveling Salesman around Lake

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

# initialization
min_cost = 10**8
a_len = len(a_list)

for i in range(len(a_list)):
    a = a_list[i]
    ushiro_i = 0
    mae_i = 0
    # 1つ後ろを取る
    if i-1<0:
        ushiro_i = a_len - 1
    else:
        ushiro_i = i - 1

    # 1つ前を取る
    if i+1>=a_len:
        mae_i = 0
    else:
        mae_i = i + 1

    # update
    kouho_1 = 0
    kouho_2 = 0
    if a_list[mae_i]-a_list[i]<0:
        kouho_1 = K - (a_list[mae_i] - a_list[i] + K)
    else:
        kouho_1 = K - (a_list[mae_i] - a_list[i])
    if a_list[i]-a_list[ushiro_i]<0:
        kouho_2 = K - (a_list[i] - a_list[ushiro_i] + K)
    else:
        kouho_2 = K - (a_list[i] - a_list[ushiro_i])
        
    min_cost = min(min_cost, kouho_1, kouho_2)

# output
print(min_cost)

Submission status: Accepted

Solution code:
import copy

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

now = 0
ans = 2000000000000000000000000

for i in range(1, n):
    now = k-a[i]+a[i-1]
    if now < ans:
      ans = now

if a[n-1]-a[0] < ans:
  ans = a[n-1]-a[0]
        
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

k,n = map(int,input().split())
a = list(map(int,input().split()))
b = []
for v in range(n-1):
    b.append(a[v+1]-a[v])

b.append(k-a[n-1]+a[0])
anss = max(b)
ans = k - anss
print(str(ans))

Submission status: Accepted

Solution code:
# C - Traveling Salesman around Lake
import numpy as np

K, N = map(int, input().split())
A = list(int(x) for x in input().split())
A.append(A[0]+K)

A = np.array(A)
B = np.diff(A, n=1)

print(sum(B)-max(B))

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-1):
	cur_dist = a[i+1] - a[i]
	if cur_dist > max_dist:
		max_dist = cur_dist

cur_dist = k + a[0] - a[-1]
if cur_dist > max_dist:
	max_dist = cur_dist

print(k - max_dist)

Submission status: Accepted

Solution code:
K, N = [int(x) for x in input().split(" ")]
a = [int(x) for x in input().split(" ")]
a.sort()
a.insert(0,a[-1])
max_d = 0
for i in range(0,N):
    if a[i+1] - a[i] >= 0 and a[i+1] - a[i] >= max_d:
      max_d = a[i+1] - a[i]
    elif a[i+1] - a[i] < 0 and a[i+1] - a[i] +K >= max_d:
      max_d = a[i+1] - a[i] + K
      
print(K-max_d)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    K, N = MAP()
    A = LIST()

    ans = INF
    for i in range(N):
        if i == 0:
            ans = A[i+N-1] - A[i] if A[i+N-1] - A[i] < ans else ans
        else:
            ans = K + A[(i+N-1)%N] - A[i] if K + A[(i+N-1)%N] - A[i] < ans else ans
    
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

A.sort()

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())
A=list(map(int,input().split()))
a=A[N-1]-A[0]
for i in range(1,N):
    if i!=N-1:
        a=min(a,K+A[i-1]-A[i],K+A[i+1]-A[i])
    else:
        a=min(a,K+A[i-1]-A[i])
print(a)

Submission status: Accepted

Solution code:
import sys

def main():
    K, N = list(map(int, sys.stdin.readline().rstrip().split()))
    data = list(map(int, sys.stdin.readline().rstrip().split()))

    def iterate_difference(index):
        try:
            yield data[index + 1] - data[index]
        except IndexError:
            raise StopIteration

    difference = set()
    for x in range(N):
        try:
            difference.add(next(iterate_difference(x)))
        except StopIteration:
            continue
    else:
        difference.add(K - data[N - 1] + data[0])

    print(K - max(difference))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout
Pi = lambda x: stdout.write(str(x) + '\n')
S = lambda x: x*(x+1) // 2
I = lambda x: 1+(2*x)
R = lambda:stdin.readline()
Ri = lambda x:map(int,x.split())
Rs = lambda x:map(str,x.split())
Rf = lambda x:map(float,x.split())
 
def main():	
	# t = int(R())
	for x in stdin:
		k,n = Ri(x)
		A = list(Ri(R()))
		ans = A[-1] - A[0]
		for i in range(n-1):
			ans = min(ans, (A[i]-A[0]) + (k-A[i+1]+A[0]))
			# Pi(ans)
		
		Pi(ans)

if __name__=='__main__':
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
data = [input().split(" ") for i in range(2)]
lake = data[0]
house = data[1]
housedata = house[0]
houseend = house[int(lake[1])-1]
result = []
result.append(int(housedata)+int(lake[0])-int(houseend))
for detail in house:
  if detail!=housedata:  
    aida = int(detail) - int(housedata)
    result.append(int(aida))
    housedata=detail
max = max(result)
print(int(lake[0])-max)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,N = map(int,input().split(" "))
A = [int(i) for i in input().split(" ")]
a1 = [i for i in A if i<=K/2]
a2 = [j for j in A if j>K/2]

Max = 0
if len(a1)==0:
    print(a2[-1]-a2[0])
elif len(a2)==0:
    print(a1[-1]-a1[0])
else:
    for i in range(len(a1)-1):
        if a1[i+1] - a1[i] > Max:
            Max = a1[i+1] - a1[i]
            
    for j in range(len(a2)-1):
        if a2[j+1] - a2[j]>Max:
            Max = a2[j+1] - a2[j]
            
    if a1[0]+K-a2[-1]>Max:
        Max = a1[0]+K-a2[-1]
        
    if a2[0]-a1[-1]>Max:
        Max = a2[0]-a1[-1]
        
    print(K-Max)

Submission status: Accepted

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

Submission status: Accepted

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

nums = [int(e) for e in input().split()]

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

short = 0
# print(nums[1])
# print(n[int(nums[1]-1)])

n.append(nums[0] + n[0])
# print(n)
# print(range(nums[1]))

# short = n[1] - n[0]

for i in range(nums[1]):
    # if i < int(nums[1]-1):
    # print("a",n[i+1], n[i])
    if n[i+1] - n[i] >= short:
        short = n[i+1] - n[i]

print(nums[0] - short)