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

#!/usr/bin/env python3
import copy
import sys

MOD = 1000000007  # type: int


def debug(s):
    print(s)


def solve(N: int, K: int, a: "List[int]"):
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N + 1):
        ai = a[i - 1]
        dp[i][0] = 1
        for k in range(1, K + 1):
            c = dp[i - 1][k] + dp[i][k - 1]
            if k - ai - 1 >= 0:
                c -= dp[i - 1][k - ai - 1]
            dp[i][k] = c % MOD
            # debug(f"{i} kids share {k} candies: => {dp[i][k]}")
    return dp[N][K]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, K, a))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import copy
import sys

MOD = 1000000007  # type: int


def debug(s):
    print(s)


def solve(N: int, K: int, a: "List[int]"):
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N + 1):
        ai = a[i - 1]
        dp[i][0] = 1
        for k in range(1, K + 1):
            c = dp[i - 1][k] + dp[i][k - 1]
            if k - ai - 1 >= 0:
                c -= dp[i - 1][k - ai - 1]
            dp[i][k] = c % MOD
            # debug(f"{i} kids share {k} candies: => {dp[i][k]}")
    return dp[N][K]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, K, a))


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

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    temp = map(lambda x: 1<<(x-1), many_int())
    sums = sum(temp)
    treasures.append(sums)

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index-1):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

goal_index=max_index-1
if dp[goal_index]!=INF:
    print(dp[goal_index])
else:
    print(-1)



### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
### BUGGY CODE ###

n = int(input())
D = sorted(list(map(int, input().split())))[::-1]
m = int(input())
T = sorted(list(map(int, input().split())))[::-1]
for t in T:
	for i, d in enumerate(D):
		if d <= t:
			D[i] = 0
			t -= d
	if t:
		print("NO")
		exit()
else:
	print("YES")

### FIXED CODE ###

n = int(input())
D = list(map(int, input().split()))
m = int(input())
T = list(map(int, input().split()))

from collections import Counter
DC = Counter(D)
TC = Counter(T)
for k, v in TC.items():
	if v > DC[k]:
		print("NO")
		exit()
else:
	print("YES")
### BUGGY CODE ###

N = int(input())
r = [list(map(int, input().split())) for _ in range(N)]
r.sort()

l = [r[0]]
r = r[1:]
while len(r) > 0:
    x1, l1 = l[-1]
    x2, l2 = r[0]
    if (x1+l1) > (x2-l2):
        if (x1+l1) > (x2+l2):
            l.pop()
            l.append(r[0])
            r.pop(0)
        else:
            r.pop(0)
    else:
        l.append(r[0])
        r.pop(0)
print(len(l))


### FIXED CODE ###

N = int(input())
r = [list(map(int, input().split())) for _ in range(N)]
r.sort()

l = r[0]
ri = 1
ans = N
while ri < N:
    x1, l1 = l
    x2, l2 = r[ri]
    if (x1+l1) > (x2-l2):
        if (x1+l1) > (x2+l2):
            l = r[ri]
            ri += 1
        else:
            ri += 1
        ans -= 1
    else:
        l = r[ri]
        ri += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=input()

for _ in range(q):
    l,r=map(int, input().split())
    print(s[l-1:r].count('AC'))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=input()
cnt = 0
list=[0]
for i in range(0,len(s)-1):
    if s[i: i + 2] == 'AC':
        cnt += 1
    list.append(cnt)

for _ in range(q):
    l,r=map(int, input().split())
    print(list[r-1]-list[l-1])
### BUGGY CODE ###

N,W = map(int,input().split())
L=[]
for _ in range(N):
    w,v=map(int,input().split())
    L.append([w,v])

DP=[[0]*(W+1) for _ in range(N+1)]
for j in range(1,N+1):
    if L[j-1][0]<=W:
        for k in range(L[j-1][0],W+1):
            DP[j][k]=max(DP[j-1][k],DP[j-1][k-L[j-1][0]]+L[j-1][1])
        for l in range(L[j-1][0]):
            DP[j][l]=DP[j-1][l]
    else:
        for m in range(0,W+1):
            DP[j][m]=DP[j-1][m]
            
print(DP[N][W])

### FIXED CODE ###

N,W = map(int,input().split())
L=[]
for _ in range(N):
    w,v=map(int,input().split())
    L.append([w,v])

DP=[[0]*(W+1) for _ in range(N+1)]
for j in range(1,N+1):
    if L[j-1][0]<=W:
        for k in range(L[j-1][0],W+1):
            DP[j][k]=max(DP[j-1][k],DP[j-1][k-L[j-1][0]]+L[j-1][1])
        for l in range(L[j-1][0]):
            DP[j][l]=DP[j-1][l]
    else:
        for m in range(0,W+1):
            DP[j][m]=DP[j-1][m]
            
print(DP[N][W])
### BUGGY CODE ###

from collections import deque

H,W=map(int, input().split())
A=[]
for i in range(H):
  A.append(list(input()))
ds=[]
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      ds.append((i, j))

x=-1
q=deque([(i, j, 0) for i, j in ds])
for i in range(H*W):
  if not q: break
  (i, j, n)=q.popleft()
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))

print(x)

### FIXED CODE ###

def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "#") for c in input()] + [True]]
    t += [[True] * (w + 2)]
    kuro = []
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro+=[(i + 1, j + 1)]
    cnt = -1
    while kuro:
        cnt += 1
        nxt = []
        for i, j in kuro:
            ti=t[i]
            if not ti[j+1]:
                ti[j + 1]=True
                nxt += [(i, j+1)]
            if not ti[j-1]:
                ti[j - 1]=True
                nxt += [(i, j-1)]
            if not t[i - 1][j]:
                t[i - 1][j]=True
                nxt += [(i - 1, j)]
            if not t[i + 1][j]:
                t[i + 1][j]=True
                nxt += [(i + 1, j)]
        kuro = nxt
    print(cnt)
 
 
h, w = map(int, input().split())
f(h, w)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

K = int(input())
for i in range(1, 20):
    if K % 2 == 0:
        print('-1')
        break
    lis=[]
    lis.append(make_divisors(int('7'*i)))
    if K in lis:
        print(i)
        break
else:
    print(K-1)

### FIXED CODE ###

import sys
K = int(input())
if K % 2 == 0 or K % 5 == 0:
    print('-1')
    sys.exit()

A = 0
for i in range(K):
    A = (10 * A + 7) % K
    if A == 0:
        print(i+1)
        break
### BUGGY CODE ###

k,s = map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                count += 1
print(count)

### FIXED CODE ###

k,s = map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z <= k and 0 <= z:
            count += 1
print(count)
### BUGGY CODE ###

K = int(input())

if K % 2 == 0:
    print(-1)
    exit()
if K % 5 == 0:
    print(-1)
    exit()

seven = 0
for i in range(10**6):
    seven = seven * 10 + 7
    if seven % K == 0:
        print(i + 1)
        exit()

print(-1)


### FIXED CODE ###

K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()

ans = 0
ai = 0
while True:
    ai = (ai * 10 + 7) % K
    ans += 1
    if ai % K == 0:
        print(ans)
        exit()
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count ** 11 + L > N ** 10 : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(1, n+1):
    ans.append(a.index(i) + 1)
for i in ans:
    print(i)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dic = {}
for i in range(n):
    dic[a[i]] = i+1
for i in range(n):
    print(dic[i+1])
### BUGGY CODE ###

import math

n = int(input())
sum = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      sum += math.gcd(math.gcd(i,j),k)

print(sum)

### FIXED CODE ###

import math

n = int(input())
sum = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    a = math.gcd(i,j)
    for k in range(1,n+1):
      sum += math.gcd(a,k)

print(sum)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(int(n/r)+2):
    for j in range(int(n/g)+2):
        num=(n-(i*r+j*g))%b
        if num==0 and n-(i*r+j*g)>=0:
            ans+=1
print(ans)


### FIXED CODE ###

def solve():
    r,g,b,n=map(int,input().split())
    ans=0
    for i in range(int(n/r)+1):
        for j in range(int((n-(i*r))/g)+1):
            num=n-(i*r+j*g)
            if num%b==0 and num>=0:
                ans+=1
    print(ans)
solve()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
info = [[] for _ in range(N+1)] # i -> info[i] 行き先
note =[]
for _ in range(M):
    x,y = map(int,input().split())
    info[x].append(y)
    note.append(y)
note = list(set(range(1,N+1)) - set(note))
len_list = []
visited_list = []
def visited(p):
    for e in visited_list:
        if e == p:
            return True
    return False
def dfs(p, length = 0):
    # 訪問済みならlength-1をメモ
    if visited(p) is True:
        len_list.append(length-1)
    # 訪問の印を付ける
    visited_list.append(p)
    # 行き場所がなければlengthをメモ
    if info[p] == []:
        len_list.append(length)
    for d in info[p]:
        dfs(d, length + 1)
for i in note:
    dfs(i)
    visited_list.clear()
ans = max(len_list)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N,M = map(int,input().split())
ad = [[] for i in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    ad[x].append(y)

dp = [-1]*N

def rec(nodes):
    if dp[nodes] != -1:
        return dp[nodes]
    res = 0
    for ne in ad[nodes]:
        option = rec(ne)+1
        if res < option:
            res = option
    dp[nodes] = res
    return dp[nodes]

ans = 0
for i in range(N):
    res = rec(i)
    if ans < res:
        ans = res
print(ans)
### BUGGY CODE ###

from scipy.sparse import csr_matrix


def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7
    
    DP_table = [[0] for i in range(13)]
    
    # 初期化
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[i][0] = 1
    else:
        DP_table[int(digit)][0] = 1
    
    DP_table = csr_matrix(DP_table, dtype=int)
        
    transition_matrixes = {}
    for multiplier in range(13):
        for digit in range(10):
            transition_matrix = [[0 for i in range(13)] for j in range(13)]
            for k in range(13):
                transition_matrix[(digit * multiplier + k) % 13][k] = 1
            transition_matrixes[(multiplier, digit)] = csr_matrix(
                transition_matrix, dtype=int)

    for multiplier in range(13):
        transition_matrixes[multiplier] = csr_matrix(
            [[0 for i in range(13)] for j in range(13)], dtype=int)
        for digit in range(10):
            transition_matrixes[multiplier] = transition_matrixes[multiplier]\
            + transition_matrixes[(multiplier, digit)]
            
    # DP
    multiplier = 1
    for i in range(1, len(S)):
        multiplier = multiplier * 10 % 13
        digit = S[i]
        if digit == '?':
            transition_matrix = transition_matrixes[multiplier]
        else:
            transition_matrix = transition_matrixes[(multiplier, int(digit))]
        
        DP_table = transition_matrix * DP_table
        DP_table = DP_table.toarray() % MOD
        DP_table = csr_matrix(DP_table)

    print(int(DP_table[5][0].toarray()))

    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

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

import bisect
n=int(input())
l=list(map(int,input().split()))
s=''
for i in range(1,n+1):
    s+=str(l.index(i)+1)+' '
print(s)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l2=[0]*(n+1)
for i,j in enumerate(l,1):
    l2[j]=i 
print(' '.join(map(str,l2[1:])))
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
ABs = [list(map(int, input().split())) for _ in range(N)]

lists = [[] for _ in range(10**5 + 1)]
availables = []
for A, B in ABs:
    bisect.insort(lists[A], B)
    
    ans = 0
for i in range(1, M + 1):
    for b in lists[i]:
        bisect.insort(availables, b)
    if availables:
        ans += availables.pop()

print(ans)


### FIXED CODE ###

import heapq
N, M = map(int, input().split())
ABs = [list(map(int, input().split())) for _ in range(N)]

heapq.heapify(ABs)
availables = []
ans = 0
for i in range(1, M + 1):
    while ABs:
        a = heapq.heappop(ABs)
        if a[0] == i:
            heapq.heappush(availables, -a[1])
        else:
            heapq.heappush(ABs, a)
            break
    if availables:
        ans -= heapq.heappop(availables)

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

import bisect
INF = 10**9 + 1
n, m = map(int, input().split())
X, Y = [-INF, 0, INF], [-INF, 0, INF]
ABC, DEF = [], []
for i in range(n):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    X.append(a)
    X.append(b)
    Y.append(c)
    Y.append(c)
for j in range(m):
    d, e, f = map(int, input().split())
    DEF.append((d, e, f))
    X.append(d)
    X.append(d)
    Y.append(e)
    Y.append(f)
X.sort()
Y.sort()
V = [[False for y in Y] for x in X]
for a, b, c in ABC:
    j = bisect.bisect_left(Y, c)
    ia = bisect.bisect_left(X, a)
    ib = bisect.bisect_left(X, b)
    for i in range(ia, ib):
        V[i][j] = True
for d, e, f in DEF:
    i = bisect.bisect_left(X, d)
    je = bisect.bisect_left(Y, e)
    jf = bisect.bisect_left(Y, f)
    for j in range(je, jf):
        V[i][j] = True
i = bisect.bisect_left(X, 0)
j = bisect.bisect_left(Y, 0)
Q = [(i, j)]
V[i][j] = True
ans = 0
while Q:
    i, j = Q.pop()
    ans += (X[i + 1] - X[i]) * (Y[j + 1] - Y[j])
    for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        if 0 < i + di < len(X) - 1 and 0 < j + dj < len(Y) - 1:
            if not V[i + di][j + dj]:
                V[i + di][j + dj] = True
                Q.append((i + di, j + dj))
        else:
            print('INF')
            exit()
print(ans)


### FIXED CODE ###

import bisect
INF = 10**9 + 1
n, m = map(int, input().split())
X, Y = [-INF, 0, INF], [-INF, 0, INF]
ABC, DEF = [], []
for i in range(n):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    X.append(a)
    X.append(b)
    Y.append(c)
    Y.append(c)
for j in range(m):
    d, e, f = map(int, input().split())
    DEF.append((d, e, f))
    X.append(d)
    X.append(d)
    Y.append(e)
    Y.append(f)
X.sort()
Y.sort()
V = [[0 for y in Y] for x in X]
for a, b, c in ABC:
    j = bisect.bisect_left(Y, c)
    ia = bisect.bisect_left(X, a)
    ib = bisect.bisect_left(X, b)
    for i in range(ia, ib):
        V[i][j] = 1
for d, e, f in DEF:
    i = bisect.bisect_left(X, d)
    je = bisect.bisect_left(Y, e)
    jf = bisect.bisect_left(Y, f)
    for j in range(je, jf):
        V[i][j] = 1
i = bisect.bisect_left(X, 0)
j = bisect.bisect_left(Y, 0)
Q = [(i, j)]
V[i][j] = 1
ans = 0
while Q:
    i, j = Q.pop()
    ans += (X[i + 1] - X[i]) * (Y[j + 1] - Y[j])
    for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        if 0 < i + di < len(X) - 1 and 0 < j + dj < len(Y) - 1:
            if V[i + di][j + dj] == 0:
                V[i + di][j + dj] = 1
                Q.append((i + di, j + dj))
        else:
            print('INF')
            exit()
print(ans)
### BUGGY CODE ###




import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return k
    else:
        return False

n = onem()

on = []
wh = [[-1 for j in range(n)] for i in range(n)]
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]

while de:

    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif len(on[kkk[0]]) != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        if len(on[kkk[1]]) != 0 and len(on[kkk[0]]) != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)















### FIXED CODE ###

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)
### BUGGY CODE ###

from collections import deque
k,n = map(int,input().split())
a = list(map(int,input().split()))
ans = deque()
for i in range(n):
    for j in range(1,n):
        if a[j]-a[i] >= abs(a[j]-a[i]-k):
            ans.append(abs(a[j]-a[i]-k))
        else:
            ans.append(a[j]-a[i])
print(max(ans))

### FIXED CODE ###

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