Harryxun/stf_run huggingface dataset:
# YouTube2
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
input=sys.stdin.readline

def main():
    def dfs(u):
        if dis[u] > 0:
            return dis[u]
        if dis[u] == 0:
            return -1
        dis[u] = 0
        res = 1
        for v in to[u]:
            tmp = dfs(v) + 1
            if tmp == 0: return -1
            res = max(res, tmp)
        dis[u] = res
        return res

    to = defaultdict(list)
    n = int(input()[:-1])
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
    all_game = n * (n - 1) // 2
    dis = [-1] * all_game
    game = [[0] * n for _ in range(n)]
    u = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            game[i][j] = game[j][i] = u
            u += 1

    for i in range(n):
        ai=a[i]
        gi=game[i]
        j = ai[0]
        pre = gi[j]
        for gi in range(1, n - 1):
            j = ai[gi]
            to[pre].append(gi[j])
            pre = gi[j]
#    print(to)

    ans=0
    for i in range(all_game):
        tmp=dfs(i)
        if tmp == -1:
            print(-1)
            exit()
        if tmp>ans:
            ans=tmp
#    print(dis)
    print(ans)

main()


### FIXED CODE ###

# YouTube1

def main():
    n = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split()))[::-1] for _ in range(n)]
    #    print(a)
    gam = []  # １日のgames
    # 初期化
    for i in range(n):
        ii = a[i][-1]
        if ii < i: continue
        if a[ii][-1] == i:
            gam.append([i, ii])
    days = 0
    fin = [False] * n
    fin_cnt = 0
    #    print(gam)
    while 1:
        days += 1
        pla = []  # 今日試合があったplayers
        for i, ii in gam:
            a[i].pop()
            a[ii].pop()
            pla.append(i)
            pla.append(ii)
        gam = []
        dec = set()
        for i in pla:
            if fin[i]: continue
            if not a[i]:
                fin[i] = True
                fin_cnt += 1
                if fin_cnt == n:
                    print(days)
                    exit()
                continue
            if i in dec: continue
            ii = a[i][-1]
            if a[ii][-1] == i:
                gam.append([i, ii])
                dec.add(ii)
        if not gam:
            print(-1)
            exit()

main()
from functools import reduce
from math import gcd
n,x = map(int,input().split())
X = list(map(int,input().split()))
X = [abs(x-X[0]) for x in X]
print(reduce(gcd,X))

### FIXED CODE ###

from functools import reduce
from fractions import gcd
n,x = map(int,input().split())
X = list(map(int,input().split()))
X = [abs(a-x) for a in X]
print(reduce(gcd,X))
N=int(input())
X=input()
a=int(X,2)

def popcount(x):
  return str(bin(x)).count("1")

pl=a%(popcount(a)+1)
if popcount!=1:
  mi=a%(popcount(a)-1)

def f(x):
  if x==0:
    return 1
  else:
    return f(x%popcount(x))+1

for i in range(N):
  if X[i]=='0':
    b=pl
    b+=pow(2,N-i-1,popcount(a)+1)
    b%=popcount(a)+1
  else:
    if popcount(a)-1!=0:
      b=mi
      b-=pow(2,N-i-1,popcount(a)-1)
      b%=popcount(a)-1
    else:
      print(0)
  print(f(b))

### FIXED CODE ###

N=int(input())
X=input()
a=int(X,2)

def popcount(x):
  return bin(x).count("1")
p=X.count('1')

pl=a%(p+1)
if p!=1:
  mi=a%(p-1)

def f(x):
  if x==0:
    return 1
  else:
    return f(x%popcount(x))+1

for i in range(N):
  if X[i]=='0':
    b=pl
    b+=pow(2,N-i-1,p+1)
    b%=p+1
  else:
    if p!=1:
      b=mi
      b-=pow(2,N-i-1,p-1)
      b%=p-1
    else:
      print(0)
      continue
  print(f(b))
import math
h,w = map(int,input().split())
if h==1 or w==1:
  print(1)
else:
  nos = math.ceil(w/2)*math.ceil(h/2) + math.floor(w/2)*math.floor(h/2)
  print(nos)


### FIXED CODE ###

a,b,c= map(int, input().split())
if ((a+c)==b*2):
 print('YES')
else:
 print('NO')
X, N = map(int, input().split())
p = list(map(int, input().split()))
for d in range(X + 1):
for s in [-1, +1]:
a = X + s * d
if p.count(a) == 0:
print(a)
exit(0)


### FIXED CODE ###

X, N = map(int, input().split())
p = list(map(int, input().split()))
for d in range(X + 1):
    for s in [-1, +1]:
        
        a = X + s * d
        if p.count(a) == 0:
            print(a)
            exit(0)
n,k=map(int,input().split())
S=[] #[ネタ種類、おいしさ]のリスト
for i in range(n):
    S.append(list(map(int,input().split())))
S.sort(reverse=1,key=lambda x:x[1])

netano_min=min(S[j][0] for j in range(n))
for i in range(n):
    S[i][0]-=netano_min-1

neta=max(S[j][0] for j in range(n)) #ネタの種類数

F=[0 for i in range(neta+1)] #ネタi種のときの美味しさの和の最大値のリスト

ma=sum(S[i][1] for i in range(k))

neta_s=len(set([S[i][0] for i in range(k)]))

netano_min=min(S[j][0] for j in range(n))

F[neta_s]=ma

#print(S)
#print(F)
#print(ma)

netalist=[0 for i in range(n)] #i種類目のネタを使った個数
keseru=[] #ネタに重複がある寿司のリスト(消してもいい寿司)
for i in range(k):
    if netalist[S[i][0]]>=1 :
        keseru.append(S[i])
        
    netalist[S[i][0]]+=1

#print(keseru)
#print(netalist)

right=len(keseru)-1
left=k
i=neta_s+1
while i<=k and right>=0 :
    while netalist[S[left][0]]!=0 :
        left+=1
    netalist[S[left][0]]+=1
    F[i]=F[i-1]+S[left][1]-keseru[right][1]
    right-=1
    left+=1
    i+=1

#print(F)
for j in range(neta_s,i+1-1) :
    F[j]+=j**2

print(max(F))


### FIXED CODE ###

n,k=map(int,input().split())
S=[] #[ネタ種類、おいしさ]のリスト
for i in range(n):
    S.append(list(map(int,input().split())))
S.sort(reverse=1,key=lambda x:x[1])

netano_min=min(S[j][0] for j in range(n))
for i in range(n):
    S[i][0]-=netano_min-1

neta=max(S[j][0] for j in range(n)) #ネタの種類数

F=[0 for i in range(neta+1)] #ネタi種のときの美味しさの和の最大値のリスト

ma=sum(S[i][1] for i in range(k))

neta_s=len(set([S[i][0] for i in range(k)]))

netano_min=min(S[j][0] for j in range(n))

F[neta_s]=ma

#print(S)
#print(F)
#print(ma)

netalist=[0 for i in range(n+1)] #i種類目のネタを使った個数
keseru=[] #ネタに重複がある寿司のリスト(消してもいい寿司)
for i in range(k):
    if netalist[S[i][0]]>=1 :
        keseru.append(S[i])
        
    netalist[S[i][0]]+=1

#print(keseru)
#print(netalist)

right=len(keseru)-1
left=k
i=neta_s+1
while len(keseru)>0 and i<=k and right>=0 and left<=n-1 :
    while left<=n-1 and netalist[S[left][0]]!=0 :
        left+=1
    if left==n :
        break
    netalist[S[left][0]]+=1
    F[i]=F[i-1]+S[left][1]-keseru[right][1]
    right-=1
    left+=1
    i+=1

#print(F)
for j in range(neta_s,i+1-1) :
    F[j]+=j**2

print(max(F))
a, b = map(int, input().split())

if (a * b % 2 == 0):
	print("Even")
else:
	print("Odd")
hibiki@hibiki-MB-E410:~/

### FIXED CODE ###

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

if (a * b % 2 == 0):
	print("Even")
	print()
else:
	print("Odd")
	print()
n, k = map(int, input().split())
p = list(map(int, input().split()))
l = [0] * n
ans = []
l[0] = (p[0] + 1) / 2
for i in range(1, n):
    l[i] = l[i - 1] + (p[i] + 1) / 2
for i in range(n - k):
    ans.append(l[i + k] - l[i])
print(max(ans))

### FIXED CODE ###

input1 = input().split()
input2 = list(map(int,input().split()))
U = input()
S = input1[0]
T = input1[1]
A = input2[0]
B = input2[1]
if U == S:
  A -= 1
else:
  B -= 1
print(str(A) + " " + str(B))
S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60
print(h,':',m,":",s ,")
#print("{a}:{b}:{c}".format(h,m,s))

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60
print(h,':',m,":",s , sep ="")
#print("{a}:{b}:{c}".format(h,m,s))
# coding: utf-8
# Your code here!
import numpy as np
import math

A, B, C, D = map(int, input().split())
sub = abs(A - B)
num1 , num2, num3 = (sub // C + 1), (sub // D + 1), (sub // (C * D // math.gcd(C, D))) + 1
print(num1, num2, num3)
        
print(sub - num1 - num2 + num3 + 1)


### FIXED CODE ###

# coding: utf-8
# Your code here!
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
    
a, b, c, d = map(int,input().split())
def cal(i, j, k):
    return i // j + i // k - i // lcm(j, k)

if a % c == 0 or a % d == 0:
    print(b - a - (cal(b, c, d) - cal(a, c, d)))
else:
    print(b - a - (cal(b, c, d) - cal(a, c, d)) + 1)
n=int(input())
for _ in range(n):
  m,f,r = map(int,input().split())
  s = m+f

if s >= 80:
    print("A")
elif s >= 65 and s < 80:
    print("B")
elif (s >= 50 and s < 65) or f >= 50:
    print("C")
elif s >= 30 and s < 50:
    print("D")
else:
    print("F")


if m == f == r== -1:
    print("F")



### FIXED CODE ###

while True:
    m, f, r = map(int, input().split())
    if m == f == r== -1:
        break
    s = m + f
    if m == -1 or f == -1:
        print("F")
    elif s >= 80:
        print("A")
    elif s >= 65:
        print("B")
    elif s >= 50:
        print("C")
    elif s >= 30:
        if r >= 50:
            print("C")
        else:
            print("D")
    else:
        print("F")
from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""
q=int(input())
lr_ary = []
for _ in range(q):
  lr_ary.append(list(map(int, input().split())))

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            print(j)
            prime[j] = False

for l,r in lr_ary:
    ret=0
    for x in range(l,r+1,2):
        if prime[x] and prime[(x+1)/2]:
            ret += 1
    print(ret)

### FIXED CODE ###

from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
ruiseki=0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        ruiseki+=1
    prime2017[x] = ruiseki
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    print(prime2017[r]-prime2017[l-1])
N = int(input())
S = list(input())
K = int(input())

print(S[K])

for i in range(N):
    if(S[i] != S[K]):
        S[i] = '*'

S = "".join(S)

print(S)

### FIXED CODE ###

N = int(input())
S = list(input())
K = int(input())

for i in range(N):
    if(S[i] != S[K-1]):
        S[i] = '*'

S = "".join(S)

print(S)
import itertools
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
def kaijo(n):
  if n== 1:
    return n
  return n * kaijo(n-1)
N_kaijo = kaijo(N)
a = []
for i in range(N):
  a.append(str(i+1))
X = list(itertools.permutations(a,N))
for i in range(len(X)):
  if P == X[i]:
    p_number = i+1
  if Q == X[i]:
    q_number = i+1
if p_number > q_number:
  ans = p_number - q_number
else:
  ans = q_number - p_number
print(ans)


### FIXED CODE ###

import itertools
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
def kaijo(n):
  if n== 1:
    return n
  return n * kaijo(n-1)
N_kaijo = kaijo(N)
a = []
for i in range(N):
  a.append(i+1)
X = list(itertools.permutations(a,N))
p_number = 0
q_number = 0
for i in range(len(X)):
  s = []
  for j in range(N):
    s.append(X[i][j])
  if s == P:
    p_number = i+1
  if s == Q:
    q_number = i+1
if p_number > q_number:
  ans = p_number - q_number
else:
  ans = q_number - p_number
print(ans)
def solve(x,y,k):
    if x==y==0: return []
    if x+y>=2*k and x>=k: return [(k,0)]+solve(x-k,y,k)
    if x+y>=2*k and y>=k: return [(0,k)]+solve(x,y-k,k)
    if x<0: return [(-x,y) for x,y in solve(-x,y,k)]
    if y<0: return [(x,-y) for x,y in solve(x,-y,k)]
    if x>y: return [(x,y) for y,x in solve(y,x,k)]
    if x+y<K and (x+y)%2==1: return solve(x,y+k,k)+[(0,-k)]
    if K&1 and x+y>k and (x+y)%k%2==0: return solve(x,y-k,k)+[(0,k)]
    z=(x+y)//2
    return [(k-z+x,z-x),(z-k,z)]
K,X,Y=map(int, open(0).read().split())
if K%2==0 and (X+Y)%2==1:
    print(-1)
else:
    ans=solve(X,Y,K)
    print(len(ans))
    ax,ay=0,0
    for x,y in ans:
        ax+=x
        ay+=y
        print(ax,ay)

### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
def solve(x,y,k):
    if x==y==0: return []
    if x<0: return [(-x,y) for x,y in solve(-x,y,k)]
    if y<0: return [(x,-y) for x,y in solve(x,-y,k)]
    if x>y: return [(x,y) for y,x in solve(y,x,k)]
    if (x+y)%k==0: return [(k,0)]*(x//k)+[(0,k)]*(y//k)+([]if x%k==y%k==0 else[(x%k,y%k)])
    if x+y>=2*k:
        if x%k+y%k>=k: return [(k,0)]*(x//k)+[(0,k)]*(y//k)+solve(x%k,y%k,k)
        else: return ([(k,0)]*(x//k)+[(0,k)]*(y//k))[:-1]+solve(x%k,y%k+k,k)
    if x+y<K and (x+y)%2==1: return solve(x,y+k,k)+[(0,-k)]
    if K&1 and x+y>k and (x+y)%k%2==0: return solve(x,y-k,k)+[(0,k)]
    z=(x+y)//2
    return [(k-z+x,z-x),(z-k,z)]
K,X,Y=map(int, open(0).read().split())
if K%2==0 and (X+Y)%2==1:
    print(-1)
else:
    ans=solve(X,Y,K)
    print(len(ans))
    ax,ay=0,0
    for x,y in ans:
        ax+=x
        ay+=y
        print(ax,ay)
def get_verteces_in_subtree():
    mem = {}
    
    def func(vertex):
        if vertex in mem.keys():
            return mem[vertex]
        
        children = tree_dictionary[vertex]
        if len(children) == 0:
            answer = [vertex]
        else:
            answer = [vertex] + sum([func(child) for child in children], [])
        mem[vertex] = answer
        return answer
    return func
  
  get_verteces_in_subtree = get_verteces_in_subtree()

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

tree_dictionary = {i: [] for i in range(1, N+1)}
for edge in edges:
    tree_dictionary[edge[0]].append(edge[1])

counts = [0] * N
for op in operations:
    top_vertex, value = op
    added_verteces = get_verteces_in_subtree(top_vertex)
    for v in added_verteces:
        counts[v-1] += value

output = ""
for c in counts:
    output += (str(c) + " ")
output = output[:-1]
print(output)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def dfs(point, pre):
    connected_vertices = all_connected_vertices[point]
    for c in connected_vertices:
        if c == pre:
            continue
        counts[c-1] += counts[point-1]
        dfs(c, point)
    
dfs(1, -1)
    
print(*counts)
N = int(input())
K = int(input())

ans = 0
for i in range(N):
    x = int(input())
    ans += 2*min(x,K-x)
print(ans)

### FIXED CODE ###

N = int(input())
K = int(input())

x = input().split()

ans = 0
for i in range(N):
    ans += 2*min(int(x[i]), K-int(x[i]))
    
print(ans)
n,z,w=map(int,input().split())
aa=input().split()
an,am=int(aa[-1]),int(aa[-2])
print(max(abs(an-w),abs(an-am)))

### FIXED CODE ###

n,z,w=map(int,input().split())
aa=input().split()
an=int(aa[-1])
if len(aa) > 1:
    am=int(aa[-2])
    print(max(abs(an-w),abs(an-am)))
else:
    print(abs(an-w))
#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    
   	if A > 9 or B > 9:
      print(-1)
    else:
      print(A * B)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(N, L)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    
    if A > 9 or B > 9:
        print(-1)
    else:
        print(A * B)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()
string = input()
num = int(input())

count=1
out =string[0]
# for s in string:
#     if count==num:
#         out=out+string[len(out)*num]
#         count=1
#     else:
#         count=count+1
# print(out)

for i,s in zip([i for i in range(len(string))],string):
    if i != 0:
        if i%num == 0:
            out=out+string[i]
print(out)


### FIXED CODE ###

l = input().split()
if int(l[0])+int(l[1])==15:
    print('+')
elif int(l[0])*int(l[1]) ==15:
    print('*')
else:
    print('x')
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if b-a > k:
  print(':(')
  exit()
else
  print('Yay!')

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if b-a > k:
  print(':(')
  exit()
elif c-a > k:
  print(':(')
  exit()
elif d-a > k:
  print(':(')
  exit()
elif e-a > k:
  print(':(')
  exit()
else:
  print('Yay!')
N, M = map(int, input().split())
A = list(map(int, input().split()))

need_matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

max_num_dict = {}
for a in A:
    if need_matches[a] in max_num_dict:
        if a > max_num_dict[need_matches[a]]:
            max_num_dict[need_matches[a]] = a
    else:
        max_num_dict[need_matches[a]] = a

useful_num_list = list(max_num_dict.values())
dp = [0] * (N+1)
for i in range(1, N+1):
    max_scale = -1
    for num in useful_num_list:
        if need_matches[num] <= i:
            scale = dp[i-need_matches[num]] + 1
            if max_scale < scale:
                max_scale = scale
    dp[i] = max_scale

useful_num_list.sort(reverse=True)
ans =""
n = N
while n > 0:
    ans_scale = ""
    for num in useful_num_list:
        if dp[n] - 1 == dp[n - need_matches[num]]:
            ans_scale = str(num)
            n -= need_matches[num]
            break
    ans += ans_scale
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
useful_num_list = list(map(int, input().split()))

need_matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    max_scale = -1
    for num in useful_num_list:
        if need_matches[num] <= i:
            scale = dp[i-need_matches[num]] + 1
            if max_scale < scale:
                max_scale = scale
    dp[i] = max_scale

useful_num_list.sort(reverse=True)
ans = 0
n = N
while n > 0:
    for num in useful_num_list:
        if n < need_matches[num]:
            continue
        if dp[n] - 1 == dp[n - need_matches[num]]:
            ans += num * (10**(dp[n]-1))
            n -= need_matches[num]
            break
print(ans)
s = list(input())
s2 = []
for i in range(len(s)):
    s2.append(s[i])
s2 = list(set(s2))
s2.sort()
s3 = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
if s2 == s3:
    print('None')
else:
    for i in range(int(len(s3))):
        if s2[i] != s3[i]:
            print(s3[i])
            break

### FIXED CODE ###

s = list(input())
s2 = []
for i in range(len(s)):
    s2.append(s[i])
s3 = list(set(s2))
s3.sort()
s4 = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
if s3 == s4:
    print('None')
else:
    for i in range(int(len(s3))):
        if s3[i] != s4[i]:
            print(s4[i])
            break
        if i == len(s3)-1:
            print(s4[i+1])
N=int(input())
A=[]
for i in range(1:10):
  for j in range(1:10):
    A.append(i*j)
 if N in A:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N=int(input())
list=[]
for i in range(1,10):
  for j in range(1,10):
    list.append(i*j)
if N in list:
   print("Yes")
else:
   print("No")
inpt = input()
cap = {Q,W,E,R,T,Y,U,I,O,P,A,S,D,F,G,H,J,K,L,Z,X,C,V,B,N,M}
if inpt in cap:
    print('A')
else:
    print('a')

### FIXED CODE ###

inpt = input()
cap = {'Q','W','E','R','T','Y','U','I','O','P','A','S','D','F','G','H','J','K','L','Z','X','C','V','B','N','M'}
if inpt in cap:
    print('A')
else:
    print('a')
import numpy as np
N = int(input())
M = int(input())

hairetu = np.ones((N+2, M+2))

for i in range(M+2):
    hairetu[0][i] = 0
    hairetu[N+1][i] = 0
for i in range(N+2):
    hairetu[i][0] = 0
    hairetu[i][M+1] = 0

for i in range(1, N+1):
    for j in range(1, M+1):
        for k in range(-1, 2):
            for l in range(-1, 2):
                hairetu[i+k][j+l] = (-1) * hairetu[i+k][j+l]


print(hairetu)
count = 0

for i in range(1, N+1):
    for j in range(1, M+1):
        if hairetu[i][j] == -1:
            count += 1


print(count)

### FIXED CODE ###

K = input().split()
N = int(K[0])
M = int(K[1])

if N >= 2 and M >= 2:
    print((N-2)*(M-2))
elif N == 1 and M >= 2:
    print(M-2)
elif N >= 2 and M == 1:
    print(N-2)
elif N == 1 and M == 1:
    print(1)
import math 

N2,M1 = map(int, input().split())

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


count = combinations_count(N2,2)

count += combinations_count(M1,2)

print(count)

### FIXED CODE ###

import math 

N2,M1 = map(int, input().split())
count=0
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if N2!=0 and N2!=1:
    count += combinations_count(N2,2)
if M1!=0 and M1!=1:
    count += combinations_count(M1,2)

print(count)
import math
import numpy
K = int(input())

total = 0
tmp =0
 for a in range(1,K+1) :
     for b in range(1,K+1) :
        tmp=math.gcd(a,b)
         for c in range(1,K+1) :
             total += math.gcd(tmp,c)

print(total)


### FIXED CODE ###

import math
import numpy
K = int(input())

total = tmp = 0
for a in range(1,K+1) :
  for b in range(1,K+1) :
   tmp=math.gcd(a,b)
   for c in range(1,K+1) :
      total += math.gcd(tmp,c)

print(total)
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

x = I()
ans = (x // 500) * 1000
x %= 500
ans += x // 5 * 5
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,n = LI()
a = LI()
ans = a[-1] - a[0]
for i in range(1,n-1):
    ans = min(ans, a[i] + (k - a[i+1]))
print(ans)