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

#input
N = int(input())
S = [sorted(input()) for i in range(N)]

ana = 0
for s1 in S:
    for s2 in S:
        if s1 == s2:
            ana += 1

print(int((ana - N) / 2))

### FIXED CODE ###

import collections

#input
N = int(input())
S = [''.join(sorted(input())) for i in range(N)]

S = collections.Counter(S)

ans = 0
for k, v in S.items():
    ans += v * (v-1) // 2

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

n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    #array = [[0]*nb for i in range(na)]
    array = [[0 for i in range(nb)] for j in range(na)]
    for i in range(na):
        for j in range(nb):
            c = 0
            if i==0:
                if a[i]==b[j]:
                    array[i][j]=1
            elif j==0:
                if a[i]==b[j]:
                    array[i][j]=1
            else:
                if a[i] == b[j]:
                    c = 1
                array[i][j] = max(
                    array[i-1][j],
                    array[i][j-1],
                    array[i-1][j-1]+c)
    print(array[na-1][nb-1])


### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def MAP(): return map(int, input().split())
inf = sys.maxsize

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
    hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
    hdiv.append(1)
    sh = sum(hdiv)
    tmpans = sh - 1
    partsum = [0 for _ in range(sh)]
    j = 0
    while j < w: #O(2 * 10 ** 3)
        tmp = 0
        idx = 0
        for kk in range(h): #O(10)
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                tmp = 0
                idx += 1
        flag = True
        for kk in range(sh): #O(10)
            if partsum[kk] > k:
                tmpans += 1
                for l in range(sh):
                    partsum[l] = 0
                flag = False
                break
        if flag:
            j += 1
    ans = min(ans, tmpans)
print(ans)


### FIXED CODE ###

import sys
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int, sys.stdin.readline().strip().split())
    s = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(h)]
    
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        partsum_p = [0 for _ in range(sh)]
        j = 0
        for j in range(w): #O(10 ** 3)
            tmp = 0
            idx = 0
            flag = False
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum_p[idx] = partsum[idx]
                    partsum[idx] += tmp
                    if partsum[idx] > k and not flag:
                        tmpans += 1
                        flag = True
                    tmp = 0
                    idx += 1
            if flag:
                partsum = [partsum[l] - partsum_p[l] for l in range(sh)]
                partsum_p = [0 for _ in range(sh)]
                for kk in range(sh):
                    if partsum[kk] > k:
                        tmpans = inf
                        break
        ans = min(ans, tmpans)
    print(ans)
### BUGGY CODE ###

from collections import deque

def bfs(maze, visited, s, h, w):
  queue = deque(s)
  #　返り値
  va = 0
  while queue:
    y,x = queue.popleft()
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if new_x < 0 or new_x >= w or new_y < 0 or new_y >=h :
        continue
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        #　移動回数の計算
        visited[new_y][new_x] = visited[y][x] + 1
        va = max(va,visited[new_y][new_x])
        queue.append([new_y, new_x])
  return va
############

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

maze = [['.' for j in range(w)] for i in range(h)]
visited = [[-1]*(w) for _ in range(h)]
s = []
s_append = s.append
for i in range(h) :
  m1 = input()
  for j in range(w) :
    if m1[j] == '#' :
      s_append([i,j])
      visited[i][j] = 0

print(bfs(maze, visited, s, h, w))

### FIXED CODE ###

from collections import deque

def bfs(maze, visited, s, h, w):
  queue = deque(s)
  #　返り値
  va = 0
  while queue:
    y,x = queue.popleft()
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if new_x < 0 or new_x >= w or new_y < 0 or new_y >=h :
        continue
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        #　移動回数の計算
        visited[new_y][new_x] = visited[y][x] + 1
        va = max(va,visited[new_y][new_x])
        queue.append([new_y, new_x])
  return va
############

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

maze = [['' for j in range(w)] for i in range(h)]
for i in range(h) :
  m1 = input()
  for j in range(w) :
    maze[i][j] = m1[j]

visited = [[-1]*(w) for _ in range(h)]
ans = []
s = []
s_append = s.append
for sy in range(h) :
  for sx in range(w):
    if maze[sy][sx] == '#' :
      s_append([sy,sx])
      maze[sy][sx] = '.'
      visited[sy][sx] = 0

print(bfs(maze, visited, s, h, w))
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1
    S = [input().strip("\n") for _ in range(H)]
    M = [[-1 for w in range(W)] for h in range(H)]
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                M[h][w] = -2
    move = ((-1, 0), (0, -1), (1, 0), (0, 1))
    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            M[h][w] = dist
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and M[h+dh][w+dw] == -1:
                        if (dh, dw) in move:
                            heappush(q, (dist, h+dh, w+dw))
                        else:
                            heappush(q, (dist + 1, h+dh, w+dw))
    print(M[fh][fw])


    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    S = [input().strip("\n") for _ in range(H)]

    q = deque()
    P = [[-1 for _ in range(W)] for h in range(H)]
    q.append((0, sh, sw))
    while q:
        d, h, w = q.popleft()
        if P[h][w] == -1:
            P[h][w] = d
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and P[h+dh][w+dw] == -1:
                        if abs(dh) + abs(dw) == 1:
                            q.appendleft((d, h+dh, w+dw))
                        else:
                            q.append((d+1, h+dh, w+dw))
    print(P[fh][fw])
    

    return 0

if __name__ == "__main__":
    solve()
### BUGGY 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():
    N, K = LI()
    A = LI()

    hq = [(-i, i, 1) for i in A]
    heapq.heapify(hq)
    
    for _ in range(K):
        _, a, d = heapq.heappop(hq)
        heapq.heappush(hq, (-a / (d + 1), a, d + 1))

    # print(hq)
    ans_t = heapq.heappop(hq)
    print(math.ceil(-ans_t[0]))

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():
    N, K = LI()
    A = LI()

    # 最大の長さがxになるような切断回数
    def cut_num(x):
        ret = sum([math.ceil(i / x) - 1 for i in A])
        return ret

    ng = 0
    ok = max(A)
    while abs(ok-ng)>10**(-6):
        m = (ng+ok)/2
        if cut_num(m) <= K:
            ok = m
        else:
            ng = m

    print(math.ceil(ok))

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

s = str(input())
t = str(input())

# pad a character to the first because i want to count index from 1
s = "." + s; t = "." + t;

a = len(s)
b = len(t)

dp = [[0]*(b) for _ in range(a)]
# dp[i][j] is the length of lcs of s[0]s[1]...s[i] and t[0]t[1]...t[j]
last = [[[0]*2 for i1 in range(b)] for i2 in range(a)]

for i in range(1, a):
    for j in range(1, b):
        if s[i] == t[j]:
            if dp[i][j] < dp[i-1][j-1] + 1:
                dp[i][j] = dp[i-1][j-1] + 1
                last[i][j] = [i, j]
        else:
            for adja in [[i-1, j-1], [i-1, j], [i, j-1]]:
                if dp[i][j] < dp[adja[0]][adja[1]]:
                    dp[i][j] = dp[adja[0]][adja[1]]
                    last[i][j] = last[adja[0]][adja[1]]


ans = ''
x, y = last[a-1][b-1]
while x > 0 and y > 0:
    ans += s[last[x][y][0]]
    x, y = last[x][y]
    x -= 1; y -= 1;

#print(*dp, sep = '\n')
print(ans[::-1])



### FIXED CODE ###

s = str(input())
t = str(input())

# pad a character to the first because i want to count index from 1
s = "." + s; t = "." + t;

a = len(s)
b = len(t)

dp = [['']*(b) for _ in range(2)]
# dp[i][j] is the length of lcs of s[0]s[1]...s[i] and t[0]t[1]...t[j]

for i in range(1, a):
    for j in range(1, b):
        if s[i] == t[j]:
            if len(dp[i&1][j]) < len(dp[(i+1)&1][j-1]) + 1:
                dp[i&1][j] = dp[(i+1)&1][j-1] + s[i]
        else:
            for adja in [[i-1, j-1], [i-1, j], [i, j-1]]:
                if len(dp[i&1][j]) < len(dp[adja[0]&1][adja[1]]):
                    dp[i&1][j] = dp[adja[0]&1][adja[1]]

print(dp[(a+1)&1][b-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))

query = []
for _ in range(q):
    query.append(list(map(int, input().split())))

for n, x, m in query:
    l = []
    for i in range(k):
        l.append(d[i]%m)
    zero = l.count(0)
    total = x%m
    total += sum(l)*((n-1)//k)
    zero_total = zero*((n-1)//k)

    s = n
    n -= 1
    n -= n//k * k
    t = 0
    for i in range(n):
        t += l[i]
    total += t
    for i in range(n):
        if l[i] == 0:
            zero_total += 1

    print(s-1-total//m-zero_total)


### FIXED CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [None]*q
for i in range(q):
    query[i] = list(map(int, input().split()))

def answer_query(n, x, m):
    l = [m if i%m == 0 else i%m for i in d]
    count = n // k
    rem = n % k
    s = sum(l)
    total = s%m * count + x%m
    for i in range(rem):
        total += l[i]

    total //= m
    total += s//m * count

    print(n-total)


for n, x, m in query:
    answer_query(n-1, x, m)
### BUGGY CODE ###

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

n_list = [i for i in range(n)]

cnt = 0
for i in n_list:
  cnt_j = 0
  pi = p[i]
  j_list = [j for j in range(i+1)]
  for j in j_list:
    if pi <= p[j]:
      cnt_j += 1
    else:
      break
  if cnt_j == i+1:
    cnt += 1
print(cnt)


### FIXED CODE ###

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

cnt = 0
p_min = p[0]
for i in range(n):
  pi = p[i]
  if pi <= p_min:
    cnt += 1
    p_min = pi
print(cnt)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
for i in range(q):
  l,r = map(int,input().split())
  count = 0
  pre = s[l-1]
  skip = False
  for j in range(l, r):
    if skip:
      skip = False
      pre = s[j]
      continue
    if pre == 'A' and s[j] == 'C':
      count += 1
    elif s[j] != 'A':
      skip = True
    pre = s[j]
  print(count)

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
c = []
pre = ""
count = 0
for i in range(n):
  if pre == "A" and s[i] == "C":
    count += 1
  pre = s[i]
  c.append(count)
  
for i in range(q):
  l,r = map(int,input().split())
  print(c[r-1]-c[l-1])
### BUGGY CODE ###

from math import sqrt
cash = {}
def isprime(n):
    if n in cash:
        return cash[n]
    if n == 1:
        cash[n] = 0
        return 0
    if n == 2:
        cash[n] = 1
        return 1
    if n % 2 == 0:
        cash[n] = 0
        return 0
    for i in range(3,int(sqrt(n)+1))[0::2]:
        if n % i == 0:
            cash[n] = 0
            return 0
    cash[n] = 1
    return 1

from sys import stdin
#cash2 = {}
for i in stdin:
    i = int(i)
    c = sum(isprime(n) for n in range(2,i+1)[1::2]) + 1
    print(c)

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
### BUGGY CODE ###

def calc_sum(i, p, k):
    r = 0
    for j in range(k):
        r = r + p[i + j]
    return r


if __name__ == '__main__':
    n, k = list(map(int, input().split(" ")))
    p = list(map(int, input().split(" ")))

    max_sum = 0
    for i in range(n - k + 1):
        # print(i, p, k)
        r = calc_sum(i, p, k)
        # print(r)
        if r > max_sum:
            max_sum = r

    print((max_sum / 2) + (k * 0.5))

### FIXED CODE ###

from collections import deque

if __name__ == '__main__':
    n, k = list(map(int, input().split(" ")))
    p = list(map(int, input().split(" ")))

    d = deque([0])
    for i in range(n):
        d.append(d[i] + p[i])

    # print(d)

    max_sum = 0
    rangeN = n - k + 1

    for i in range(rangeN):
        max_sum = max(max_sum, d[i + k] - d[i])
    # print(max_sum)

    # r_array = [sum(p[i:i + k]) for i in range(rangeN)]
    print((max_sum / 2) + (k * 0.5))
### BUGGY CODE ###

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

L.sort()

counter=0
i=0
while i<N-2:
  j=i+1
  k=j+1
  while j<N-1:
    if L[i]+L[j]>L[k]:
      if k<N-1:
        counter+=1
        k+=1
      else:
        counter+=1
        j+=1
        k=j+1
    else:
      j+=1
      if j==k:
        k+=1
  i+=1
  
print(counter)

### FIXED CODE ###

def f(list, n):
  length=len(list)
  if list[-1]<n:
    return length
  elif list[0]>=n:
    return 0
  else:
    a=length//2
    b=length//4
    while b>=1:
      if list[a]<n:
        a+=b
      else:
        a-=b
      b=b//2
      
    if list[a]<n:
      while list[a+1]<n:
        a+=1
    else:
      while list[a]>=n:
        a-=1
        
    return a+1  

n=int(input())
l=list(map(int, input().split()))
l.sort()
counter=0
for i in range(n-2):
  for j in range(i+1, n-1):
    counter+=f(l[(j+1):], l[i]+l[j]) #f(list, n) counts num in the sorted list under n
    
print(counter)
### BUGGY CODE ###

import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = sys.stdin.readline()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    N = 14
    K = 2
    S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  i = 0
  lenSC = len(SC) - 1
  ans = 0
  for i in range(0,lenSC+1,2):
  #while i <= lenSC:
    cnt = 0
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    k += 1
    cnt = sum(SC[i:k])
    if ans < cnt:
      ans = cnt
  # i += 2

  print(ans)

main()

### FIXED CODE ###

import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = sys.stdin.readline()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    # N = 14
    # K = 2
    # S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    N = 5
    K = 1
    S = "11111"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  SH = []
  cnt = 0
  for i in range(len(SC)):
    cnt += SC[i]
    SH.append(cnt)
  
  if 'get_ipython' in globals(): print(SH)
  
  lenSC = len(SC) - 1
  ans = 0
  for i in range(0,lenSC+1,2):
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    if i != 0:
      cnt = SH[k] - SH[i-1]
    elif k == i:
      cnt = SH[k]
    else:
      cnt = SH[k] - SH[i]
    if ans < cnt: ans = cnt

  print(ans)

main()
### BUGGY CODE ###

#!/usr/bin/env python3
import bisect

n = int(input())
s = list(input())
rind = []
gind = []
bind = []

for index, val in enumerate(s):
    if val == 'R':
        rind.append(index)
    if val == 'G':
        gind.append(index)
    if val == 'B':
        bind.append(index)

# 1つめの条件を満たすものを求めてから
# 2つめの条件を満たすものを引く
ans = len(rind)*len(gind)*len(bind)
sans = 0
# R,G,B
for i in rind:
    for j in gind:
        if i < j and (j-i)+j in bind:
            sans += 1
# R,B,G
for i in rind:
    for j in bind:
        if i < j and (j-i)+j in gind:
            sans += 1
# G,B,R
for i in gind:
    for j in bind:
        if i < j and (j-i)+j in rind:
            sans += 1
# G,R,B
for i in gind:
    for j in rind:
        if i < j and (j-i)+j in bind:
            sans += 1
# B,R,G
for i in bind:
    for j in rind:
        if i < j and (j-i)+j in gind:
            sans += 1
# B,G,R
for i in bind:
    for j in gind:
        if i < j and (j-i)+j in rind:
            sans += 1

print(ans-sans)

### FIXED CODE ###

#!/usr/bin/env python3

n = int(input())
s = list(input())

rnum = s.count('R')
gnum = s.count('G')
bnum = s.count('B')
ans = rnum * gnum * bnum
for i in range(n):
    for j in range(n):
        d = i+j 
        f = d+j 
        if f>=n:
            break
        if s[i]!=s[d] and s[d]!=s[f] and s[f]!=s[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

S = input()
T = input()
N = len(S)
M = len(T)

dp = [ [0]* (len(T)+1) for _ in range(len(S)+1)]

for i in range(1, len(S)+1):
    for j in range(1,len(T)+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = max(dp[i][j] , dp[i-1][j-1] + 1)
        else:
            dp[i][j] = max(dp[i][j] , dp[i-1][j], dp[i][j-1], dp[i-1][j-1] )
res = []

i = N
j = M
cnt = dp[N][M]
while cnt :
    while cnt == dp[i][j]:
        i -= 1
    i += 1
    while cnt == dp[i][j]:
        j -= 1
    j += 1
    res.append(S[i-1])
    cnt -= 1
    i -= 1; j -= 1
print("".join(reversed(res)))

### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4011183

S,T = input(), input()
S,T = list(map(lambda x: ord(x)-97, S)), list(map(lambda x: ord(x)-97, T))

# print(S,T)

dp = [ [0] * (len(T)+1)] + [[0]+[None]*len(T) for _ in range(len(S))]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        dp[i+1][j+1] = max(
                dp[i][j+1], 
                dp[i+1][j],
                dp[i][j] + (s==t)
                )
res = []

x,y = len(S), len(T)

while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        res.append(chr(S[x]+97))
print(''.join(reversed(res)))
### BUGGY CODE ###

c = [[0 for i in range(1001)] for j in range(1001)]
def lcs(X, Y):
    global c
    m, n = len(X), len(Y)
    for i in range(m+1):
        c[i][0] = 0
    for j in range(n+1):
        c[0][j] = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])
    return c[m][n]

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))


### FIXED CODE ###

def lcs(X, Y):
    global c
    m, n = len(X), len(Y)
    c = [[0 for i in range(n+1)] for j in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])
    return c[m][n]

def lcs_improved(X, Y):
    hist = [0] # yの文字cまでを見た時に, hist[i]以降の文字列において, 共通文字のうち, 一番小さいindexのもの
    for c in Y:
        for i in range(len(hist)-1, -1, -1):
            next_match_i = X.find(c, hist[i])+1
            if next_match_i:
                if i+1 < len(hist):
                    hist[i+1] = min(hist[i+1], next_match_i)
                else:
                    hist.append(next_match_i)
    return len(hist)-1

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs_improved(X, Y))
### BUGGY CODE ###

def main():
    k, n = map(int, input().split())
    a = list(map(int, input().split()))

    d = [a[i] - a[i-1] for i in range(1, n)]
    d.insert(0, a[0])
    d.append(k - a[-1])

    d = tuple(d)
    
    most_min_path = 10000

    for i in range(n):
        if i == 0:
            normal_ck = sum(d) - d[i] - d[-1]
            reverse_ck = sum(d) - d[i+1]
        elif i == n - 1:
            normal_ck = sum(d) - d[i]
            reverse_ck = sum(d) - d[i+1] - d[0]
        else:
            normal_ck = sum(d) - d[i]
            reverse_ck = sum(d) - d[i+1]

        min_ck = normal_ck if normal_ck < reverse_ck else reverse_ck
        if most_min_path > min_ck:
            most_min_path = min_ck

    print(most_min_path)


if __name__ == '__main__':
    main()

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(a[0] + k)

d = [a[i+1] - a[i] for i in range(n)]
l = 0
for i in range(n):
    l = max(l, a[i+1] - a[i])
print(k - l)