Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

INF=10**15

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self,s):

        import heapq
        que=[]
        D=[INF*(L+1)+L] * self.V
        D[s]=0
        heapq.heappush(que,(0,s))

        while len(que)!=0:
            cost,v=heapq.heappop(que)

            if cost>D[v]:
                continue

            for i in range(len(self.G[v])):
                e=self.G[v][i]
                a=D[e.to]
                nokori=L-cost%(L+1)
                if nokori>=e.cost:
                    new=cost+e.cost
                else:
                    new=(cost//(L+1)+1)*(L+1)+e.cost
                if a>new:
                    D[e.to]=new
                    heapq.heappush(que,(D[e.to],e.to))

        return D

import sys

input=sys.stdin.readline

N,M,L=map(int,input().split())
city=Dijkstra(N)
for i in range(0,M):
    a,b,c=map(int,input().split())
    if L>=c:
        city.add(a-1,b-1,c)
        city.add(b-1,a-1,c)

ans=[city.shortest_path(i) for i in range(0,N)]

Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if ans[s-1][t-1]!=INF*(L+1)+L:
        print(ans[s-1][t-1]//(L+1))
    else:
        print(-1)


### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N,M,L=map(int,input().split())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

data=floyd_warshall(csr2)
ans=[]
Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if data[s-1][t-1]!=float('inf'):
        ans.append(int(data[s-1][t-1])-1)
    else:
        ans.append(-1)

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

S = input()

ans = 0

## 4桁
for i in range(0, len(S)-3):
  for j in range(i+3, len(S)):
    if int(S[i:j+1]) % 2019 == 0:
      ans += 1

print(ans)

### FIXED CODE ###

S = input()[::-1]
 
## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)
### BUGGY CODE ###

import itertools
n=int(input())
a=list(map(int,input().split()))
b=0
for v in itertools.combinations(a,2):
  b+=v[0]*v[1]
print(b%(10**9+7))  

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sum(a)
c=0
for v in range(n-1):
  b-=a[v]
  c+=a[v]*b
print(c%(10**9+7))
### BUGGY CODE ###

n = int(input())
height = [int(x) for x in input().split()]
cnt =0

for i_index, i in enumerate(height[:-1]):
    if i+i_index >= n:
        continue

    for j_index, j in enumerate(height[i_index+i:]):
        if j+i == j_index+i:
            cnt += 1
            
            

print(cnt)

### FIXED CODE ###

# n = int(input())
# height = [int(x) for x in input().split()]
# cnt =0

# for i_index, i in enumerate(height[:-1]):
#     if i+i_index >= n:
#         continue

#     for j_index, j in enumerate(height[i_index+i+1:]):
#         if j+i == j_index+i+1:
#             cnt += 1
#             # print(i,j,j_index)
            
# print(cnt)
def count(dic,x):
    if x in dic:
        dic[x]+=1
    else:
        dic[x]=1
 
N=int(input())
A=list(map(int,input().split()))
dic1={}
dic2={}
s=0
for i in range(N):
    count(dic1,i-A[i])
    count(dic2,i+A[i])
for x in dic1:
    if x in dic2:
        s+=dic1[x]*dic2[x]
print(s)
### BUGGY CODE ###

# coding: utf-8


def yakusu(n):
    ans = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i != i:
                ans.append(n // i)

    return sorted(ans)


def main():
    N = int(input())

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

    is_in_A_flag = [0] * (10**6+1)

    for a in A:
        is_in_A_flag[a] += 1

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        # for b in B[i][:-1]:
        for j in range(len(B[i])-1):
            b = B[i][j]
            if is_in_A_flag[b] > 0:
                is_ans = False
                break

        if is_ans:
            if is_in_A_flag[B[i][-1]] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())


### FIXED CODE ###

# coding: utf-8

# 13:42- kaisetsu and try again
# -14:03 giveup (WA*6) -> testcase


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] == -1:
            continue

        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0

        for i in range(2, M+1):
            if a*i > M:
                break
            is_ans_flag[a*i] = 0

        n_appeared_in_A[a] = -1

    return sum(is_ans_flag)


print(main())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, k = map(int, input().split())
A = sorted([int(i) for i in input().split()])
F = sorted([int(i) for i in input().split()], reverse = True)
P = [A[i]*F[i] for i in range(n)]

if sum(A) <= k: print('0')
else:
    new_P = list(A)
    i=0
    while k < sum(new_P):
        for j in range(n):
            if (P[j] - i) > 0: new_P[j] = (P[j] - i) // F[j] + 1
            else: new_P[j] = 0
        i += 1
        
    for h in range(n):
        P[h] -= F[h]*new_P[h]
        
    d = k - sum(new_P)
    if d > 0:
        for di in range(d):
            m = max(P)
            mi = P.index(m)
            P[mi] -= F[mi]      
        
    print(max(P))

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
n, k = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort(reverse = True)
F = [int(i) for i in input().split()]
F.sort()
"""
n = 11
k = 14
A = [1,1,2,3,3,4,5,5,5,6,9]
F = [9,9,8,8,7,6,4,3,3,2,2]
"""

 
P = [A[i]*F[i] for i in range(n)]
sum_A = sum(A)
 
def b(p):
    result = 0
    for i in range(n):
        if P[i] > p:
            r = (P[i] - p) // F[i]
            if P[i] - r * F[i] > p:
                r += 1
            result += r
    return result
 
if sum_A <= k: print('0')
else: 
    left = 0
    right = max(P)
    middle = int((left + right) / 2)
    bm = b(middle)
    
    
    
    while right - left > 1:
        
        if bm > k: left = middle
        else: right = middle
            
        middle = int((left + right) / 2)
        bm = b(middle)
 
    if b(left) <= k: print(left)
    else: print(right)
### BUGGY CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N = i()
A = l()
ans = []

for i in itertools.combinations(A,N-1):
    a = 0
    for j in i:
        a = a ^ int(j)
    ans.append(str(a))
ans.reverse()
print(" ".join(ans))


### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

def xor(x,y):
    return x^y

N = i()
A = l()
ans = []
S = xor(A[0],A[1])

for i in range(len(A)-2):
    S = xor(S,A[i+2])

for i in A:
    ans.append(str(xor(S,i)))

print(" ".join(ans))
### BUGGY CODE ###

def isPrime(x):
    if x==2:
        return True
    if x<2 or x%2==0:
        return False
    i=3
    while i*2<=x:
        if x%i==0:
            return False
        i+=2
    return  True

n=input()
ct=0
for i in xrange(n):
    if isPrime(input()):
        ct+=1
print(ct)

### FIXED CODE ###

def isPrime(x):
    if x==2:
        return True
    if x<2 or x%2==0:
        return False
    if pow(2,x-1,x)==1:
        return True
    else:
        return False

n=input()
ct=0
for i in xrange(n):
    if isPrime(input()):
        ct+=1
print(ct)
### BUGGY CODE ###

import sys 
input=sys.stdin.readline
from collections import deque

N=int(input())
L=[[]]

for i in range(N):
    a=deque(map(int,input().split()))
    L.append(a)
#print(L)

day=0
cnt=0
for i in range(10**6+5):
    if cnt==N*(N-1)/2:
        break
    D=dict()
    CNT=0
    for j in reversed(range(1,N+1)):
        #print(L[j],j)
        if len(L[j])==0 or j in D:
            continue
        elif L[L[j][0]][0]==j and L[j][0] not in D:
            D[j]=1
            D[L[j][0]]=1
            X=L[j][0]
            L[j].popleft()
            L[X].popleft()
            CNT+=1
    if CNT==0:
        print(-1)
        exit()
    cnt+=CNT
    day+=1
#print(L)
#print(cnt)
print(day)

### FIXED CODE ###

N=int(input())
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)
    
#print(A)
B=[0 for i in range(N+1)]
C=[a for a in range(1,N+1)]
cnt=0
for i in range(10**6):
    D=[]
    F=0
    for j in C:
        if A[A[j][B[j]]][B[A[j][B[j]]]]==j and j not in D and A[j][B[j]] not in D:
            D.append(j)
            D.append(A[j][B[j]])
            B[A[j][B[j]]]+=1
            B[j]+=1
            F=1
            cnt+=1
            #print("A",i,B,D)
            #print(A[j][B[j]],B,D)
    if F==0:
        break
    D.sort()
    C=D
    
if cnt==N*(N-1)//2:
    print(i)
else:
    print(-1)
### BUGGY CODE ###

from collections import deque
k=int(input())
if not k&1:
    print(-1)
    exit()
ks=str(k)
tmp=-1
carries=deque()
carries.append(0)
d1=int(ks[-1])

mul=0
i=1
while i<10**7:
    flag=False
    car=carries.pop()
    for j in range(0,10):
        if (d1*j+car)%10==7:
            cr=(car+k*j)//10
            if len(str(cr))==str(cr).count('7'):
                print(i+len(str(cr)))
                exit()
            carries.append(cr)
            flag=True
            break
    if not flag:
        print(-1)
        exit()
    i+=1

### FIXED CODE ###

k=int(input())
mod=7
cnt=1
for i in range(k):
    if mod%k==0:
        print(cnt)
        exit()
    mod=(mod*10+7)%k
    cnt+=1
print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)
    
stack = [1]
dp = [[] for _ in range(n+1)]
dp[1] = [a[0]]
ans = [1]*(n+1)
checked = []
while stack:
    b = stack.pop()
    if b in checked:
        continue
    checked.append(b)
    e = dp[b]
    x = len(e)
    for i in t[b]:
        if i in checked:
            continue
        stack.append(i)
        c = a[i-1]
        if e[-1] < c:
            dp[i] = e.copy()+[c]
            ans[i] = x+1
        else:
            dp[i] = e.copy()
            ans[i] = x
        d = dp[i]
        for j in range(x-1,-1,-1):
            if j == 0 and d[j] > c:
                d[j] = c
            elif d[j] > c and d[j-1] < c:
                d[j] = c
                
for i in ans[1:]:
    print(i)

### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**7)

n = int(input())
a = [0]+list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)

m = 10**18
dp = [m]*(n+1)
ans = [1]*(n+1)
checked = [False]*(n+1)
checked[1] = True
changes = []

def search(x):
    ind = bisect.bisect_left(dp,a[x])
    changes.append((ind,dp[ind]))
    dp[ind] = a[x]
    ans[x] = bisect.bisect_left(dp,m)
    
    for i in t[x]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

n = int(input())
commands = []
for a in range(n):
    raw = input().split()
    try:
        commands.append([raw[0], int(raw[1])])
    except:
        commands.append([raw[0], 'none'])

result = []
for a in commands:
    command, x = a[0], a[1]
    if command == 'insert':
        result.append(x)
    elif command == 'delete':
        if x in result:
            if result.count(x) == 1:
                result.remove(x)
            else:
                for i in range(len(result)-1, -1, -1):
                    if result[i] == x:
                        del result[i]
                        break
        else:
            continue
    elif command == 'deleteFirst':
        del result[-1]
    else:
        del result[0]

for i in range(len(result)-1, -1, -1):
    if i == 0:
        print(result[i])
    else:
        print(result[i], end=' ')


### FIXED CODE ###

from collections import deque
import sys

n = int(input())
result = deque()
func = {'insert':result.appendleft,\
        'delete':result.remove,\
        'deleteFirst':result.popleft,\
        'deleteLast':result.pop}

for line in sys.stdin.readlines():
    c = line.split()
    if len(c) > 1:
        try:
            func[c[0]](int(c[1]))
        except:
            continue
    else:
        func[c[0]]()

print(*result)
### BUGGY CODE ###

h,w = map(int,input().split())

INF = 10 ** 18
grid = [input() for _ in range(h)]

ans = 0
for sy in range(h):
    for sx in range(w):
        if grid[sy][sx] == ".":
            for gy in range(h):
                for gx in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if grid[gy][gx] == ".":

                        dist = [[INF] * w for _ in range(h)]
                        
                        dist[sy][sx] = 0
                        q = [(sy,sx)]
                        d = 1
                        
                        while q:
                          qq = []
                          for y,x in q:
                            for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                              yy,xx = y+dy, x+dx
                              if not 0 <= xx < w:
                                  continue
                              if not 0 <= yy < h:
                                  continue
                              if grid[yy][xx] == '#':
                                continue
                              if dist[yy][xx] != INF:
                                continue
                              dist[yy][xx] = d
                              qq.append((yy,xx))
                          q = qq
                          d += 1
                        ans = max(ans, dist[gy][gx])

print(ans)


### FIXED CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

count = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            count += 1
if count == 400:
    print(38)
    exit()

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque

N, M, K = map(int, input().split())
# F = [list(map(int, input().split())) for _ in range(M)]
# B = [list(map(int, input().split())) for _ in range(K)]

F = defaultdict(set)
for _ in range(M):
    u, v = map(int, input().split())
    F[u].add(v)
    F[v].add(u)
B = defaultdict(set)
for _ in range(K):
    u, v = map(int, input().split())
    B[u].add(v)
    B[v].add(u)

res = []
for i in range(N):
    cand = 0
    visited = [0]*N
    q = deque()
    q.append((i+1, 0))
    visited[i] = 1

    while q:
        curNode, lv = q.popleft()
        for node in F[curNode]:
            if visited[node-1] == 0:
                visited[node-1] = 1
                q.append((node, lv+1))
                if lv >= 1 and i+1 not in B[node]:
                    cand += 1

    res.append(cand)

print(' '.join(map(str, res)))


### FIXED CODE ###

from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def is_same_root(self, x, y):
        return self.find(x) == self.find(y)

    def get_group_size(self, x):
        return -self.parents[self.find(x)]

N, M, K = map(int, input().split())
uf = UnionFind(N)

friends = defaultdict(set)
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    friends[u].add(v)
    friends[v].add(u)
    uf.union(u, v)
blocks = [0]*N
for _ in range(K):
    u, v = map(lambda x: int(x)-1, input().split())
    if uf.is_same_root(u, v):
        blocks[u] += 1
        blocks[v] += 1

res = [uf.get_group_size(i)-len(friends[i])-blocks[i]-1 for i in range(N)]
print(' '.join(map(str, res)))
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
from collections import deque
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [list(readline().rstrip()) for _ in range(H)]

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '#':
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        next_que = deque()
        for h, w in que:
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '#':
                    continue
                mat[h+dh][w+dw] = '#'
                next_que.append((h+dh, w+dw))

        res += 1
        que = next_que

    print(res - 1)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
from collections import deque
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))


def main():
    H, W = map(int, readline().rstrip().split())
    mat = [list(readline().rstrip()) for _ in range(H)]

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '#':
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        flg = False
        next_que = deque()
        while que:
            h, w = que.popleft()
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '#':
                    continue
                flg = True
                mat[h+dh][w+dw] = '#'
                next_que.append((h+dh, w+dw))

        if flg:
            res += 1
        que = next_que

    print(res)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

shift = [(i*10)%13 for i in range(10)]

def main():
    S_tmp = input()
    N = len(S_tmp)-1
    S = [S_tmp[i] for i in range(N)]                          
    
    ans = [0]*13
    ans[0] = 1
    
    for i in range(N):
        ans_pre = [x for x in ans]
        ans = [0]*13
        
        if S[i] == "?":                   
            for j in range(13):                   
                for k in range(10):                           
                    ans[(j*10+k)%13] += ans_pre[j]
        else:       
            for j in range(13):
                ans[(j*10+int(S[i]))%13] += ans_pre[j]
                
        for j in range(13):
            ans[j] %= 10**9+7
            
    print(ans[5])
                
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

shift = [(i*10)%13 for i in range(10)]

def main():
    S_tmp = input()
    N = len(S_tmp)-1
    S = [S_tmp[i] for i in range(N)]                          
    
    ans = [0]*13
    ans[0] = 1
    
    for i in range(N):
        ans_pre = [x for x in ans]
        ans = [0]*13
        
        if S[i] == "?":                   
            for j in range(13):                   
                for k in range(10):                           
                    ans[(j*10+k)%13] += ans_pre[j]
        else:       
            for j in range(13):
                ans[(j*10+int(S[i]))%13] += ans_pre[j]
                
        for j in range(13):
            ans[j] %= 10**9+7
            
    print(ans[5])
                
    

if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

dis = 0
done = [A[0]]
not_done = A[1:N]

while True:
    min_d = 1e6
    for a in done:
        for b in range(len(not_done)):
            if a>b:
                d = min(abs(a-not_done[b]), abs(a-not_done[b]-K))
            else:
                d = min(abs(a-not_done[b]), abs(a-not_done[b]+K))
            min_d = min(d, min_d)
            min_idx = b
    dis += min_d
    done.append(not_done.pop(min_idx))
    if len(not_done) ==0:
        break
print(dis)


### FIXED CODE ###

import numpy as np

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

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