Harryxun/stf_run huggingface dataset:
N=int(input())
stock=[N-i for i in range(N)]

N*=2
n=-int(-N**0.5//1)
if N/n==N//n:
    yoko=N//n
else:
    print("No")
    exit()

ans=[[0 for j in range(yoko)]for i in range(n)]

for i in range(N-1):
    for j in range(i,yoko):
        temp=stock.pop(-1)
        ans[i][j]=temp
        ans[j+1][i]=temp

print("Yes")
print(len(ans))
for item in ans:
    print(len(item), *item)

### FIXED CODE ###

N=int(input())
stock=[N-i for i in range(N)]

"""
if N==2:
    print("Yes")
    print(2)
    print(2,1,2)
    print(2,1,2)
    exit()
"""

N*=2
n=-int(-N**0.5//1)
if N/n==N//n and (n-N//n)==1:
    yoko=N//n
else:
    print("No")
    exit()

ans=[[0 for j in range(yoko)]for i in range(n)]

for i in range(N-1):
    for j in range(i,yoko):
        temp=stock.pop(-1)
        ans[i][j]=temp
        ans[j+1][i]=temp

print("Yes")
print(len(ans))
for item in ans:
    print(len(item), *item)
if S == "ABC"
print "ARC"
if S =="ARC"
print"ABC"

### FIXED CODE ###

S = input()
if S ==("ABC"):
  print("ARC")
else:
  print("ABC")
N = int(input())
A = list(map(int, input().split()))
L, R, df = 0, N - 1, A[0] - A[N - 1]

while R - L > 1:
    if df < 0:
        L += 1,
        df += A[L]
    else:
        R -= 1
        df -= A[R]
print(abs(df))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L, R, sumL_R = 0, N - 1, A[0] - A[N - 1]

while R - L > 1:
    if sumL_R < 0:
        L += 1
        sumL_R += A[L]
    else:
        R -= 1
        sumL_R -= A[R]
print(abs(sumL_R))
def main():
    N,K = map(int, input().split())
    p = list(map(int, input().split()))
    esum = [0]*N
    psum = [0]*(N-K)
    esum[0] = p[1]
    for i in range(1,K):
        esum[i] = esum[i-1]+p[i]
    for i in range(K,N):
        esum[i] = esum[i-1]+p[i]
        psum[i-K] = esum[i]-esum[i-K]

    print(  (max(psum)+K)*0.5  )
    return

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N,K = map(int, input().split())
    p = list(map(int, input().split()))
    if N>K:
        esum = [0]*N
        psum = [0]*(N-K)
        esum[0] = p[1]
        for i in range(1,K):
            esum[i] = esum[i-1]+p[i]
        for i in range(K,N):
            esum[i] = esum[i-1]+p[i]
            psum[i-K] = esum[i]-esum[i-K]
        ans = (max(psum)+K)*0.5
    else:
        ans = (sum(p)+K)*0.5

    print(ans)
    return

if __name__=="__main__":
    main()
a = input()
b = input()
c = input()
x = input()

cnt = 0
for i in range(a + 1):
	if 500 * i <= x:
		p = x - 500 * i
		for j in range(b + 1):
			if 100 * j <= p:
				q = p - 100 * j:
				for k in range(c + 1):
					if q - 50 * k == 0:
						cnt += 1

print(cnt)

### FIXED CODE ###

x = int(input())
a = int(input())
b = int(input())

ans = (x - a) % b
print(ans)
N=int(input())
A=list(map(int,input().split()))
ans=1
flag=0
sum_=0
for i in range(N+1):
  sum_+=A[i]
node=2
if A[0]>0:
  flag=1
  if A==[1] and N==0:
    flag==2
sum_-=A[1]
for i in range(1,N+1):
  if i!=N and node-A[i]<=0:
    flag=1
  elif i!=N:
    sum_-=A[i+1]
    ans+=node
    if 2*(node-A[i])-A[i+1]<=sum_:
      node=2*(node-A[i])
    else:
      node=sum_+A[i+1]   
  else:
    ans+=A[i]

if flag==1:
  print("-1")
elif flag==2:
  print("1")
else:
  print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
flag=0
sum_=0
for i in range(N+1):
  sum_+=A[i]
node=2
if A[0]>0:
  flag=1
  if A==[1] and N==0:
    flag=2
if N!=0:
  sum_-=A[1]
for i in range(1,N+1):
  if i!=N and node-A[i]<=0:
    flag=1
  elif i!=N:
    sum_-=A[i+1]
    ans+=node
    if 2*(node-A[i])-A[i+1]<=sum_:
      node=2*(node-A[i])
    else:
      node=sum_+A[i+1]   
  else:
    if node-A[i]<0:
      flag=1
    else:
      ans+=A[i]
if N==0 and A==[0]:
  flag=1

if flag==1:
  print("-1")
elif flag==2:
  print("1")
else:
  print(ans)
A,B=map(int,input().split())
N = list(map(int,input().split()))

c=0

for i in range(A):
  if N[i] >= B:
    c+=1
  else:
    pass
  i+=1
print(c)


### FIXED CODE ###

N = int(input())

L = [i for i in range(N+1)]

odd = []

for j in range(N+1):
  if L[j] % 2 == 0:
    pass
  else:
    odd.append(L[j])
  j+=1

print(len(odd)/(len(L)-1))
a = int(inpit())
ans = 0

if i in range(a):
  i += 1
  ans = ans + i
  
print(ans)

### FIXED CODE ###

a = int(input())
ans = 0
 
for i in range(a):
  i += 1
  ans = ans + i
  
print(ans)
from copy import copy
def gcd(a, b):
	if a%b == 0:
		return b
	else:
		return gcd(b, a%b)

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

if n==2:
	print(max(A))
	quit()

a = list(set(A))

gcds = []
for i in range(len(a)):
	temp = copy(a)
	temp.pop(i)

	num1 = temp[0]
	num2 = temp[1]
	result = gcd(num1, num2)
	for j in range(2, len(temp)):
		if result in gcds:
			break
		result = gcd(result, temp[j])
	
	if result not in gcds:
		gcds.append(result)

gcds = sorted(gcds)

if len(gcds)==1:
	print(gcds[0])
else:
	gcds = sorted(gcds)
	if len(a)==len(A):
		print(gcds[1])
	else:
		print(gcds[0])

### FIXED CODE ###

from copy import copy
def gcd(a, b):
	if a%b == 0:
		return b
	else:
		return gcd(b, a%b)

def factor(n):
	factors = [1, n]
	i=2
	while i*i <= n:
		if n%i==0:
			factors.append(i)
			factors.append(n//i)
		i+=1

	return factors

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

if n==2:
	print(max(A))
	quit()

gcd1 = 0
fac1 = sorted(factor(A[0]),reverse=True)
for i in range(len(fac1)):
	count = 0
	for j in range(1, n):
		if A[j]%fac1[i]!=0:
			count += 1
			if count >= 2:
				break
	if count <= 1:
		gcd1 = fac1[i]
		break

fac2 = sorted(factor(A[1]),reverse=True)
gcd2 = 0
for i in range(len(fac2)):
	count = 0
	for j in range(2, n):
		if A[j]%fac2[i]!=0:
			count += 1
			break
	if count <= 0:
		gcd2 = fac2[i]
		break

print(max(gcd1, gcd2))
n = int(input())

if n%2 == 0:
	print(float(1))
else:
	print(double((n//2  + 1)/ n))

### FIXED CODE ###

n = int(input())

if n%2 == 0:
	print(format(0.5, '.10f'))
else:
	print(format((n//2  + 1)/ n, '.10f'))
from functools import reduce
from operator import mul

N = int(input())
nums = list(map(int, input().split()))

multi = reduce(mul, nums)
n = 0
while multi % 2 == 0:
  nums /= 2
  multi = reduce(mul, nums)
  n += 1

print(n)


### FIXED CODE ###

def how_many_times_divisible(n):
	ans = 0
	while n % 2 == 0:
		n /= 2
		ans += 1
	return ans

n = int(input())
a = map(int, input().split())
ans = min(map(how_many_times_divisible, a))

print(ans)
d, i = 0, 0
while d <= x:
    d += L[i]
    i += 1

print(i)

### FIXED CODE ###

import numpy as np

n, x = map(int, input().split())
L = list(map(int, input().split()))

CS_L = np.cumsum(L).tolist()
ans = len([l for l in CS_L if l <= x])
print(ans + 1)
class Combination:
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    comb=Combination(n-1)
    for i in range(n-1):
        mPow=(mPow*(m-1))%mod
        modPow.append(mPow)
    for i in range(n-1-k,n):
        ans+=(((m*modPow[i])%mod)*comb(n-1,i))%mod
    print(ans%mod)
if __name__=="__main__":
    main()

### FIXED CODE ###

class Combination:
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    if n==1:
        print(m)
    elif m==1:
        if k==n-1:
            print(1)
        else:
            print(0)
    else:
        comb=Combination(n-1)
        for i in range(n-1):
            mPow=(mPow*(m-1))%mod
            modPow.append(mPow)
        for i in range(n-1-k,n):
            ans+=(((m*modPow[i])%mod)*comb(n-1,i))%mod
        print(ans%mod)
if __name__=="__main__":
    main()
from collections import defaultdict
N = int(input())
L = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        from_to[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
#print("pointed", list([un_hash(key), val] for key, val in pointed.items()))
#print("pointing", list([un_hash(key), val] for key, val in pointing.items()))
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        pointed_i = pointed[h]
        pointing_i = pointing[h]
        if pointed_i == 0:
            START.add(i)
        if pointing_i == 0:
            DST.add(i)
if len(START) == 0 or len(DST) == 0:
    print(-1)
else:
    assert 1 == 2


### FIXED CODE ###

from collections import deque

n = int(input())
matches = []
for _ in range(n):
    matches.append(list(map(lambda x: int(x)-1, input().split())))

q = deque(range(n))

days = [0]*n  # 各選手の現在の日付
pairs = [-1]*n  # 次の対戦相手を管理(wait的な)

while q:
    x = q.popleft()  # 試合する人
    if len(matches[x]) == 0:  # 試合が全て終わってる?
        continue
    y = matches[x].pop(0)  # xの次の対戦相手
    if pairs[y] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        q.append(x)
        q.append(y)
    else:
        pairs[x] = y

if not any(matches):  # 全ての試合をしょうか
    print(max(days))
else:
    print(-1)
if input() == 'A':
  print('T')
elif input() == 'T':
  print('A')
elif input() == 'C':
  print('G')
else:
  print('C')

### FIXED CODE ###

s = input()
if s == 'A':
  print('T')
elif s == 'T':
  print('A')
elif s == 'C':
  print('G')
else:
  print('C')
N, X = map(int, input().split())
L = list(input().split())
D = 1
l = [0]
if N == 1:
  print(1)
else:
  while max(l) < X:
    if int(l[-1]) + int(L[D - 1]) <= X:
      l.append(int(l[-1]) + int(L[D - 1]))
      D += 1
    else:
      break
  print(len(l))

### FIXED CODE ###

N, X = map(int, input().split())
L = list(map(int, input().split()))
l = [0]
if L[0] <= X:
  l.append(L[0])
  for x in range(N - 1):
    a = l[-1] + L[x + 1]
    if a <= X:
      l.append(a)
    elif a > X:
      break

print(len(l))
import sys
import numpy as np

#+++++
		
def main2():
	n = int(input())
	water_list=list(map(int, input().split()))
	
	mw=water_list[-1]
	for i in range(mw+1):
		cv = mw - i
		init_cv=cv
		for w in water_list[::-1]:
			#print(w,cv, w-cv)
			cv = w - cv
			if cv < 0:
				break
		else:
			#print('hhh', cv, init_cv, mw)
			if init_cv == cv:
				ret = [0 for _ in range(n)]
				cv=init_cv
				for ii, ww in enumerate(water_list):
					ret[ii] = cv*2
					cv = ww - cv
					#print(ret)
				return ret
				
	return 'hoge'
	
def main():
	n = int(input())
	water_list=list(map(int, input().split()))
	a = sum(water_list) - 2*sum(water_list[1::2])
	ret = [a]
	next=a
	for v in water_list[:-1]:
		next = (v*2 - next)
		ret.append(next)
	
	print(*ret)
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		
	ret = main()
	if ret is not None:
		print(' '.join([str(i) for i in ret]))

### FIXED CODE ###

import sys
#import numpy as np

#+++++
		
def main2():
	n = int(input())
	water_list=list(map(int, input().split()))
	
	mw=water_list[-1]
	for i in range(mw+1):
		cv = mw - i
		init_cv=cv
		for w in water_list[::-1]:
			#print(w,cv, w-cv)
			cv = w - cv
			if cv < 0:
				break
		else:
			#print('hhh', cv, init_cv, mw)
			if init_cv == cv:
				ret = [0 for _ in range(n)]
				cv=init_cv
				for ii, ww in enumerate(water_list):
					ret[ii] = cv*2
					cv = ww - cv
					#print(ret)
				return ret
				
	return 'hoge'
	
def main():
	n = int(input())
	water_list=list(map(int, input().split()))
	a = sum(water_list) - 2*sum(water_list[1::2])
	ret = [a]
	next=a
	for v in water_list[:-1]:
		next = (v*2 - next)
		ret.append(next)
	
	print(*ret)
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		
	ret = main()
	if ret is not None:
		print(' '.join([str(i) for i in ret]))
N = int(input())
S = []
for j in range(N):
    S[j]= input()
print(len(set(S)))

### FIXED CODE ###

N = int(input())
S = []
for j in range(N):
    S.append(input())
print(len(set(S)))
N, K = input().split(" ")

d_num = int(input())

okasi_nasi = set()
for i in range(d_num):
    okasi_nasi = okasi_nasi | input().split(" ")

print(len(okasi_nasi))

### FIXED CODE ###

N, K = input().split(" ")

okasi_nasi = set()
for i in range(int(K)*2):
    buf = input()
    if i % 2 == 1:
        if buf[0] != "":
            okasi_nasi = okasi_nasi | set(buf.split(" "))

print(int(N) - len(okasi_nasi))
n = int(input())
if n[-1] == 3:
  print('bon')
elif n[-1] in ['0', '1', '6', '8']:
  print('pon')
else:
  print('hon')

### FIXED CODE ###

n = input()
if n[-1] == '3':
  print('bon')
elif n[-1] in ['0', '1', '6', '8']:
  print('pon')
else:
  print('hon')
def d():
    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        ai, bi, ci = map(int, input().split())
        edges[ai].append((bi, ci))
        edges[bi].append((ai, ci))
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    for edge in edges[1:]:

        if K == edge:
            pass
    weighted_nodes = [0]*(N+1)
    def add_weight(k):
        for v in edges[k]:
            d, w = v
            if (weighted_nodes[d] != 0) or (d == K):
                continue
            weighted_nodes[d] = w + weighted_nodes[k]
            add_weight(d)
    add_weight(K)

    for q in queries:
        s, e = q
        print(weighted_nodes[s] + weighted_nodes[e])

d()


### FIXED CODE ###

from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v
#         if d != pre:
#             distance[d] = w + distance[k]
#             add_weight(d, k)
# add_weight(K, -1)
que = deque()
que.append(K); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in edges[a]:
        if distance[b] == -1:
            distance[b] = c + distance[a]
            que.append(b)

# print(distance)

for _ in range(Q):
    s, e = map(int, input().split())
    print(distance[s] + distance[e])
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W, K = LI()
    s = [SS() for _ in range(W)]

    ans = [[0] * W for _ in range(H)]
    cnt = 1
    for i in range(H):
        is_first = True
        for j in range(W):
            if s[i][j] == '#':
                if is_first:
                    is_first = False
                else:
                    cnt += 1
            ans[i][j] = cnt
        cnt += 1

    for i in ans:
        print(*i)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W, K = LI()
    s = [SS() for _ in range(H)]

    ans = [[0] * W for _ in range(H)]

    # 行ごとにいちごで区切って塗り分け
    cnt = 1
    for i in range(H):
        is_first = True
        if s[i].count("#") >= 1:
            for j in range(W):
                if s[i][j] == '#':
                    if is_first:
                        is_first = False
                    else:
                        cnt += 1
                ans[i][j] = cnt
            cnt += 1

    # いちごなし行の場合、前の行の値をコピー
    first_strawberry_row = -1
    for i in range(H):
        if s[i].count("#") >= 1:
            first_strawberry_row = i
            break

    for i in range(first_strawberry_row, H):
        if s[i].count("#") == 0:
            for j in range(W):
                ans[i][j] = ans[i-1][j]

    # 前にコピー元がない場合、後ろの行からコピー
    for i in range(first_strawberry_row):
        r = first_strawberry_row - 1 - i
        if s[r].count("#") == 0:
            for j in range(W):
                ans[r][j] = ans[r+1][j]

    for i in ans:
        print(*i)

if __name__ == '__main__':
    resolve()
n,k= map(int,input().split())
m = n - k +1 
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
print(g1)

for i in range(1,k+1):
    print(nCr(m,i,mod)*nCr(k,i-1,mod))


### FIXED CODE ###

n, k = map(int,input().split())
m = n - k + 1 
def nCr(l,r,mod):
    if (r<0 or r>l):
        return 0
    r = min(r,l-r)
    return g1[l] * g2[r] * g2[l-r] % mod
mod = 10**9 + 7
N = 10**5
g1 = [1,1]
g2 = [1,1]
inverse = [0,1]
for i in range(2,N+1):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
for i in range(1,k+1):
    print(nCr(m,i,mod)*nCr(k-1,i-1,mod)%mod)
S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m][0] + dp[k-1][i][0]) % mod)
  k += 1
print(dp[k-1][5])


### FIXED CODE ###

S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])
import sys
from copy import deepcopy
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

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

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

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

### FIXED CODE ###

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

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

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

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