Harryxun/stf_run huggingface dataset:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys
  
def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
  
# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))
  
# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]
  
# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))
  
# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])
  
# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))

### FIXED CODE ###

def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)
a,b=list(map(int,input.split()))
print(max(a+b,a-b,a*b))

### FIXED CODE ###

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

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
bunshi=1
for i in range(n):
  bunshi*=a[i]
bunbo=0
for i in range(n):
  bunbo+=bunshi//a[i]
print(float(bunshi)/float(bunbo))
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
S = 0
for i in range(0, K):
  if not A.empty():
    A.pop_back()
print(sum(A))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
S = 0
for i in range(0, K):
    if len(A) > 0:
        A.pop(-1)
print(sum(A))
from collections import Counter
def main(n:int,lst:list)->int:
    lst1 = lst[::2]
    lst2 = lst[1::2]
    c1 = Counter(lst1).most_common()
    c2 = Counter(lst2).most_common()
    if c1[0][0] == c2[0][0]:
        if len(c1)!=1 and len(c2)!=1:
            return n - max(c1[0][1] + c2[1],c2[0][1] + c1[1])
        else:
            return n//2
    else:
        return n - c1[0][1] - c2[0][1]

n = int(input())
lst = input().split()
print(main(n,lst))


### FIXED CODE ###

from collections import Counter


def solve(V):
    n = len(V)
    ac = Counter(V[::2]).most_common(2)
    bc = Counter(V[1::2]).most_common(2)

    if ac[0][0] != bc[0][0]:
        return n - ac[0][1] - bc[0][1]
    else:
        if len(bc) == 1 or len(ac) == 1:
            return n // 2
        else:
            return n - max(ac[0][1] + bc[1][1], ac[1][1] + bc[0][1])


if __name__ == "__main__":
    n = int(input())
    l = input()
    print(solve(l.split(" ")))
if __name__ == "__main__":
    for i in range(200):
        a,b = list(map(int,input().strip().split()))
        print(len(str(a+b)))

### FIXED CODE ###

import fileinput as fi
if __name__ == "__main__":
    for i in fi.input():
        a,b = list(map(int,i.strip().split()))
        print(len(str(a+b)))
S = input()
h = S // 3600
m = S % 3600 //60
s = S % 3600 % 60
print h + ':' + m + ':' + t

### FIXED CODE ###

S = input()
h = S // 3600
m = S % 3600 //60
s = S % 3600 % 60
print str(h) + ':' + str(m) + ':' + str(s)
N,X=map(int,input().split())
L=list(map(int,input().split()))
x=0
time=0
while x<=X:
    x+=L[time]
    time+=1
print(time)


### FIXED CODE ###

N,X=map(int,input().split())
L=list(map(int,input().split()))
x=0
time=0
for i in range(N+1):
  if x<=X:
    time+=1
  if i<N:
    x+=L[i]
print(time)
#120_D
#Union-Find
n,m=map(int,input().split())
edges=[]
for _ in range(m):
    a,b=map(int,input().split())
    edges.append((a-1,b-1))
edges=edges[::-1]

par=[i for i in range(n)]
size=[1 for _ in range(n)]

def find(x):#木の根を求める
    if par[x]==x:
        return x
    else:
        return find(par[x])
    
def merge(x,y):#併合
    x=find(x)
    y=find(y)
    if x==y:
        return
    par[y]=x
    size[x]+=size[y]
            
def same(x,y):
    return find(x)==find(y)
    

ans=[n*(n-1)//2 for i in range(m)]
for i in range(0,m-1):
    a,b=edges[i]
    ans[i+1]=ans[i]
    if not same(a,b):
        ans[i+1]-=size[find(a)]*size[find(b)]
        merge(a,b)
        

ans=ans[::-1]
for i in range(m):
    print(ans[i])

### FIXED CODE ###

#120_D
#Union-Find
n,m=map(int,input().split())
edges=[]
for _ in range(m):
    a,b=map(int,input().split())
    edges.append((a-1,b-1))
edges=edges[::-1]

par=[i for i in range(n)]
size=[1 for _ in range(n)]
rank=[0 for _ in range(n)]

def find(x):#木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
    
def merge(x,y):#併合
    x=find(x)
    y=find(y)
    if x==y:
        return
    if rank[x]>rank[y]:
        par[y]=x
        size[x]+=size[y]
    else:
        par[x]=y
        size[y]+=size[x]
        if rank[x]==rank[y]:
            rank[y]+=1
            
def same(x,y):
    return find(x)==find(y)
    

ans=[n*(n-1)//2 for i in range(m)]
for i in range(0,m-1):
    a,b=edges[i]
    ans[i+1]=ans[i]
    if not same(a,b):
        ans[i+1]-=size[find(a)]*size[find(b)]
        merge(a,b)
        

ans=ans[::-1]
for i in range(m):
    print(ans[i])
n,d = map(int,input().split())

for i in range(1,21):
  if (i - d) == 1:
    num = i + d
    ans = n / num 
    if ans = int(ans):
      print(ans)
    else:
      print(ans+1)

### FIXED CODE ###

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

ans = n / (2 * d + 1)
if ans == int(ans):
    print(int(ans))
    exit()
else:
    print(int(ans) + 1)
    exit()
N = int(input())
return(N*(N+1)//2)

### FIXED CODE ###

N = int(input())
print(int(N*(N+1)/2))
S = input()
cnt = 0
temp = S[0]
for s in S:
    if s == temp:
        cnt += 1
    else:
        cnt = 0
        temp = s
    if s >= 3:
        print("Yes")
        exit()
print("No")
        

### FIXED CODE ###

S = input()
cnt = 0
temp = S[0]
for s in S[1:]:
    if s == temp:
        cnt += 1
    else:
        cnt = 0
        temp = s
    if cnt >= 2:
        print("Yes")
        exit()
print("No")
a = input()
b = input()
int(a)
int(b)

if a<=9 anf b<=9:
  print(a*b)
  else:
    print(-1)

### FIXED CODE ###

a,b=map(int, input().split())
if a<=9 and b<=9:
  print(a*b)
else:
  print(-1)
n,m=map(int,input().split())
a=list(map(int,input().split()))
c=0
while True:
    a.sort()
    a1=a[:n//2]
    a2=a[n//2:]
    while True:
        if c==m:
            print(sum(a1)+sum(a2))
            exit()
        if len(a2)==0:
            a=a1
            break
        k=a2.pop(-1)
        while True:
            k=k//2
            c+=1
            if k<=a1[-1]:
                a1.append(k)
                break

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
for i in range(m):
  min = heapq.heappop(a)
  heapq.heappush(a, (-min//2)*(-1))
print(-sum(a))
import collections
from scipy import special

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

for i in range(0, n):
    target_list = num_list[0:i] + num_list[i+1:]
    target_items = collections.Counter(target_list).items()
    ans = 0

    for item in target_items:
        if item[1] > 1:
            ans += special.comb(item[1], 2, True)

    print(ans)

### FIXED CODE ###

import collections

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

cnt = collections.Counter(num_list)
ttl = 0
for v in cnt.values():
    ttl += v*(v-1)//2
for a in num_list:
    print(ttl - (cnt[a] - 1))
N,A,B=map(int,input().split())
print(min(N*a,B))

### FIXED CODE ###

N,A,B=map(int,input().split())
print(min(N*A,B))
n = int(input())

ia = []
ib = []
for i in range(n):
    a, b = map(int, input().split())
    ia.append((i, a))
    ib.append((i, b))

ia.sort(key=lambda x:x[1])
ib.sort(key=lambda x:x[1])

ans = 0
for i in range(n):
    if i % 2 == 0:
        if ia[0][1] == ia[-1][1]:
            j, b = ib.pop()
            _, a = ia.pop(j)
        else:
            j, a = ia.pop()
            _, b = ib.pop(j)
        ans += a
    else:
        if ib[0][1] == ib[-1][1]:
            j, a = ia.pop()
            _, b = ib.pop(j)
        else:
            j, b = ib.pop()
            _, a = ia.pop(j)
        ans -= b
print(ans)


### FIXED CODE ###

n = int(input())

ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a+b, a, b))

ab.sort(key= lambda x:x[0])

ans = 0
for i in range(n):
    v, a, b = ab.pop()
    if i % 2 == 0:
        ans += a
    else:
        ans -= b

print(ans)
from decimal import *

a,b,c=map(int,input().split())
a,b,c=Decimal(a),Decimal(b),Decimal(c)
if c**0.5>a**0.5+b**0.5:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

from decimal import *

a,b,c=map(int,input().split())
a,b,c=Decimal(a),Decimal(b),Decimal(c)
if (max(0,c-(a+b)))**2>4*a*b:
  print('Yes')
else:
  print('No')
import statistics as stats
from math import factorial


def nCr(n, r):
    return int(factorial(n)/factorial(n-r)/factorial(r))


def main():
    N, A, B = tuple(map(int, input().split(' ')))
    max_ave = 0
    v_list = sorted(list(map(int, input().split(' '))), reverse=True)

    bucket_min = v_list[A-1]
    bucket_max = v_list[0]
    max_bucket = v_list[:A]

    max_ave = stats.mean(max_bucket)

    all_num = v_list.count(bucket_min)
    bucket_num = max_bucket.count(bucket_min)


    print(max_ave)
    if bucket_min == bucket_max:
        if all_num >= B:
            print(2**B-1)
        else:
            num = 0
            for i in range(A, B+1):
                num += nCr(all_num, i)
            print(num)
    else:
        print(nCr(all_num, bucket_num))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math


def C(n,r):
    fact = math.factorial
    return fact(n) // fact(r) // fact(n-r)

def main():
    N, A, B = tuple(map(int, input().split(' ')))
    v = list(map(int, input().split(' ')))

    v.sort(reverse=True)

    print(sum(v[:A])/A)

    a, b = v.count(v[A-1]), v[:A].count(v[A-1])

    if v[0] == v[A-1]:
        print(sum([C(a, r) for r in range(A, min(B, a)+1)]))
    else:
        print(C(a, b))



if __name__ == '__main__':
    main()
n, gap = int(input()), []
data = list(map(int, [input() for i in range(n)]))
cnt, g = 0, n
while g >= 1:
    g //= 2
    gap.append(g)
if gap[0]:
    gap.remove(0)
m = len(gap)
for i in range(m):
    for idx in range(gap[i], n):
        j = idx - gap[i]
        while j >= 0 and data[j] > data[j+gap[i]]:
            data[j+gap[i]], data[j] = data[j], data[j+gap[i]]
            j -= gap[i]
            cnt += 1
print(m)
print(" ".join(map(str, gap)))
print(cnt)
for i in range(n):
    print(data[i])



### FIXED CODE ###

import sys

def shellSort(data, cnt, g, n):
    for idx in range(g, n):
        j = idx - g
        v = data[idx]
        while j >= 0 and data[j] > v:
            data[j+g] = data[j]
            j -= g
            cnt += 1
        data[j+g] = v
    return data, cnt

n, gap = int(input()), []
a = ([int(i) for i in sys.stdin.readlines()], 0)
g = 0
while g <= n//9:
    g = 3 * g + 1
    gap.append(g)
m = len(gap)
for i in gap[::-1]:
    a = shellSort(a[0], a[1], i, n)
print(m)
print(" ".join(map(str, gap[::-1])))
print(a[1])
for i in range(n):
    print(a[0][i])
m, d = map(int, raw_input().split())
raw_input()
if m in (1,3,5,7,8,10,12) and d == 31:
  print(1)
elif m in (4,6,9,11) and d == 30:
  print(1)
elif m == 2 and d == 28:
  print(1)
else:
  print(0)


### FIXED CODE ###

m, d = map(int, raw_input().split())
raw_input()
if m in (1,3,5,7,8,10,12) and d == 31:
  print(1)
elif m in (4,6,9,11) and d == 30:
  print(1)
elif m == 2 and d == 28:
  print(1)
else:
  print(0)
n, p = map(int,input().split())
s = input()

mod = p
l = 100

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)


P = [0] * p

T = [1]
for i in range(n-1):
    T.append((T[-1] * 10) % p)

# a = 0
# for i in range(n):
#     a = (a * 10 + int(s[i]))
#     a = a%p
#     P[a] += 1

ans = 0
u = 0
v = 0
s = list(s)
for i in range(n):
    s[i] = int(s[i])
# for i in range(n):
#     print(u,P[(p-u)%p])
#     ans += P[(p-u)%p]
#     u = (u-int(s[n-1-i])) % p
#     u = u * inv(10%p, mod) % p
# print(s)
for i in range(n):
    v = (u * 10 + s[i]) % p
    P[v] += 1
    # qq = s[i-1] if i > 0 else 0
    ans += P[(p-v*s[i])%p]
    # print(ans)
    u = v
s -= 1
if s[-1] == 0:
    s += 1

print(ans)



### FIXED CODE ###

n, p = map(int,input().split())
s = input()

mod = p
l = 100

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

T = [1]
for i in range(n-1):
    T.append((T[-1]*10) % p)

P = [0] * p
P[0] = 1

ans = 0
v = 0
S = [int(s[i]) for i in range(n-1,-1,-1)]

if p==2 or p==5:
    for i in range(n):
        ans += (int(s[i]) % p == 0) * (i+1)
else:
    for i in range(n):
        v = (v + T[i]*S[i]) % p
        ans += P[v]
        P[v] += 1
        # print(P)

print(ans)
K,X=map(int, input().split())
if 500*K >=X:
    print("yes")
else*
    print("No")

### FIXED CODE ###

K,X=map(int, input().split())
if K*500>=X:
    print('Yes')
else:
    print('No')
a,b,c=int(input())
if c>=a+b:
  print(0,0)
elif a+b>c>=a:
  print(0,b-c+a)
else:
  print(a-c,b)

### FIXED CODE ###

a,b,c=map(int,input().split())
if c>=a+b:
  print(0,0)
elif a+b>c>=a:
  print(0,b-c+a)
else:
  print(a-c,b)
A = int(input())
B = int(input())
 
def takahashi:
  if A and B >= 1:
  	if A and B <= 9:
    
    else print('-1')
    	print(A * B)

### FIXED CODE ###

A, B = map(int, input().split())
 
if A < 10 and B < 10:
    print(A*B)
else:
    print(-1)
n, m=map(int, input().split())
a=set()
d={}
pena=0
for i in range(m):
    p, s=input().split()
    if s=="AC":
        a.add(int(p))
        pena+=d.pop(p)
    else:
        if p in d:
            d[p]+=1
        else:
            d[p]=1
print(len(a), pena)


### FIXED CODE ###

n, m=map(int, input().split())
a=set()
d={}
pena=0
for i in range(m):
    p, s=input().split()
    if s=="AC" and int(p) not in a:
        a.add(int(p))
        if p in d:
            pena+=d.pop(p)
    else:
        if p in d:
            d[p]+=1
        else:
            d[p]=1
print(len(a), pena)
h = int(input(""))
w = int(input(""))
if h*w % 2 == 0:
    print(h*w/2)
if h*2%2 == 1:
    print((h*w+1)/2)

### FIXED CODE ###

H, W = list(map(int, input().split()))
if H==1 or W==1:
    print(1)
    exit()
res = int((H+1)/2) * W
if H%2==1:
    res -= int(W/2)
print(res)
import heapq
import sys

#input = sys.stdin.readline

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

    data = [0]*N
    for i in range(N):
        S = list(str(input()))
        s = 0
        m = 0
        for j in range(len(S)):
            if S[j] == "(":
                s += 1
            else:
                s -= 1
                m = min(m,s)
        data[i] = (-m,-s)


    heapq.heapify(data)
    x = 0
    valid = []
    heapq.heapify(valid)

    det = 0

###
#print("data",data)
#print("valid",valid)
#print(x)
###

    while data or valid:
        while data and x - data[0][0] >= 0:
            y = heapq.heappop(data)
            heapq.heappush(valid,(y[1],y[0]))
    
        while valid and x >= 0:
            z = heapq.heappop(valid)
            if x - z[0] >= 0:
                x -= z[0]
            else:
                heappush(valid,z)
    
        if data and x - data[0][0] < 0:
            det = -1
            break

    if det == 0 and x == 0:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()





### FIXED CODE ###

def score(a,b):
    if b-a >= 0:
        return a
    else:
        return 10**6+1-b

N = int(input())

A = [0]*N
B = [0]*N

for i in range(N):
    S = input()
    a = 0
    b = 0
    for j in range(len(S)):
        if S[j] == ')':
            a += 1
        else:
            a -= 1
        A[i] = max(A[i],a)

        if S[-j-1] == '(':
            b += 1
        else:
            b -= 1
        B[i] = max(B[i],b)

#print('S',S)
#print('A',A)
#print('B',B)

L = sorted(list(range(N)),key = lambda i:score(A[i],B[i]))

SA = 0
SB = 0

#print('L',L)

for i in range(N):
    if SB > A[L[i]]:
        SB += B[L[i]] - A[L[i]]
    else:
        SA += A[L[i]]-SB
        SB = B[L[i]]
    #print(SA,SB)

if SA == 0 and SB == 0:
    print('Yes')
else:
    print('No')
import math
import sys
import os
from operator import mul
import sympy

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

# 約数
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N = I()
ans = 0

for i in range(1,N+1):
    ans += i * sympy.divisor_count(i)
    # print(i,sympy.divisor_count(i))

print(ans)

### FIXED CODE ###

import math
import sys
import os
from operator import mul
import numpy as np
# import sympy

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

N = I()
ans = 0

# 足し方の見方を変える。等差数列の和をKまで足す
# 1 + 2 + 3 + 4 +...
#   + 2     + 4 +...
for i in range(1,N+1):
    # Nを超えない整数
    y = N//i
    sum = y*(y+1)*i/2
    ans += sum

print(int(ans))





# 素数 エラトステネス
def seachPrimeNum(N):
   max = int(np.sqrt(N))
   seachList = [i for i in range(2,N+1)]
   primeNum = []
   while seachList[0] <= max:
       primeNum.append(seachList[0])
       tmp = seachList[0]
       seachList = [i for i in seachList if i % tmp != 0]
   primeNum.extend(seachList)
   return primeNum

# 約数
def divisor_count(n):
    divisors = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors += 1
            if i != n // i:
                divisors += 1

    return divisors
n = input()

if n == 1:
    print("HEllo World")
else:
    a, b = map(int, input().split())
    ans = a+b
    print(ans)

### FIXED CODE ###

n = int(input())

if n == 1:
    print("Hello World")
elif n ==2:
    a = int(input())
    b = int(input())
    ans = a+b
    print(ans)
import numpy as np

s = str(input())

y, m, d = s.split("/")

y, m, d = int(y), int(m), int(d)

if y < 2019:
  print("Heisei")
elif y==2019 and m<4:
  print("Heisei")
elif y==2019 and m=4 and d < 30:
  print("Heisei")
else:
  print("TBD")

### FIXED CODE ###

import numpy as np

s = str(input())
y, m, d = s.split("/")

y, m, d = int(y), int(m), int(d)

if y < 2019:
  print("Heisei")
elif y==2019 and m<4:
  print("Heisei")
elif y==2019 and m==4 and d <= 30:
  print("Heisei")
else:
  print("TBD")
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
for _ in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((-c,u))
vals = [None] * n
def dijkstra(start):
    h = [start]
    vals[start] = 0
    ans = True
    while h:
        u = h.pop()
        for d, v in ns[u]:
            if vals[v] is None:
                vals[v] = vals[u]+d
                h.append(v)
            else:
                if vals[v]!=val+d:
                    return False
    return ans

for start in range(n):
    if vals[start] is not None:
        continue
    res = dijkstra(start)
    if not res:
        print("No")
        break
else:
    print("Yes")

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
for _ in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((-c,u))
vals = [None] * n
def dijkstra(start):
    import heapq
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    ans = True
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
            else:
                if vals[v]!=val+d:
                    return False
    return ans

for start in range(n):
    if vals[start] is not None:
        continue
    res = dijkstra(start)
    if not res:
        print("No")
        break
else:
    print("Yes")
s = input()
result = []
for i in range(len(s)):
  if '0' == i[s]:
    result.append(0)
  elif '1' == i[s]:
    result.append(1)
  elif 'B' == i[s]:
    if 0 == len(result):
      pass
    else:
      result.pop()
print(result)

### FIXED CODE ###

s = input()
result = []
for i in range(len(s)):
  if 'B' == s[i]:
    if 0 == len(result):
      pass
    else:
      result.pop()
  else:
    result.append(s[i])    
print("".join(result))
import collections
import math

def combination(n, m):
    return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))

N = int(input())
S = []
for n in range(N):
    S.append(str(input()))

ans = 0
Y=[]
for s in S:
    X = []
    for w in s:
        X.append(w)
        X.sort()
        y = ''.join(X)
    Y.append(y)

print(Y)

c = collections.Counter(Y)
C = c.most_common()

len_C = len(C)
print(C)
print(len_C)

for n in range(len_C):
    if C[n][1] == 1:
        del C[n]
    else:
        pass
print(C)

len_C = len(C)

for m in range(len_C):
    ans += combination(C[m][1], 2)

print(round(ans))

### FIXED CODE ###

import collections
import math

def combination(n, m):
    return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))

N = int(input())
S = []
for n in range(N):
    S.append(str(input()))

ans = 0
Y=[]
for s in S:
    X = []
    for w in s:
        X.append(w)
        X.sort()
        y = ''.join(X)
    Y.append(y)

c = collections.Counter(Y)
C = c.most_common()
len_C = len(C)

for n in range(len_C):
    if C[n][1] > 1:
        ans += combination(C[n][1], 2)
    else:
        pass

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

dif = [A[i+1]-A[i] for i in range(N-1)]

dif.extend([K-A[N]])

print(K-max(dif))


### FIXED CODE ###

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