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

def union(group, new_mem):
    if (group[new_mem[0]-1] + group[new_mem[1]-1]) != 0 and (group[new_mem[0]-1] * group[new_mem[1]-1]) == 0:
        choice = max(group[new_mem[0]-1], group[new_mem[1]-1])
       
        group[new_mem[0]-1] = choice
        group[new_mem[1]-1] = choice
            
    elif group[new_mem[0]-1] + group[new_mem[1]-1] == 0: 

        group[new_mem[0]-1] = min(new_mem[0], new_mem[1])
        group[new_mem[1]-1] = min(new_mem[0], new_mem[1])
        
    elif (group[new_mem[0]-1] + group[new_mem[1]-1]) != 0 and (group[new_mem[0]-1] * group[new_mem[1]-1]) != 0:
        old = max(group[new_mem[0]-1], group[new_mem[1]-1])
        new = min(group[new_mem[0]-1], group[new_mem[1]-1])
        for i in range(len(group)):
            if group[i] == old:
                group[i] = new
                 
    return group

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

non_route = []
total = int(n*(n-1)/2)
non_route.append(total)

group = [0 for i in range(n)] 
for i in range(m-1,0,-1):
    group_for_calc = union(group, bridge[i]) 
    connected_group = list(set(group_for_calc)-set({0})) 
    count = 0
    if len(connected_group) == 1:
        num = group_for_calc.count(connected_group[0])
        count = int(num*(num-1)/2)

    else:
        for i in range(len(connected_group)):
            num = group_for_calc.count(connected_group[i])
            count += int(num*(num-1)/2)
    ans = total - count
    non_route.append(ans)

final = sorted(non_route)
for i in range(len(final)):
    print(final[i])

### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]
 
    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
    
n,m = map(int, input().split())
bridge = []
for i in range(m):
    a, b= map(int, input().split())
    bridge.append((a,b))

non_route = []
total = int(n*(n-1)/2)
non_route.append(total)

uft = UnionFind(n)

tmp = total

for i in range(m-1,0,-1):
    a = bridge[i][0] -1
    b = bridge[i][1] -1

    if uft.issame(a, b):
        non_route.append(non_route[-1])
        continue
    ra = uft.size(a)
    rb = uft.size(b)
    non_route.append(non_route[-1] - ra * rb)
    uft.merge(a, b)

final = sorted(non_route)
for i in range(len(final)):
    print(final[i])
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    L = sorted(map(int, input().split()))
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            for c in range(b + 1, N):
                if L[a] < L[b] + L[c] and L[b] < L[c] + L[a] and L[c] < L[a] + L[b]:
                    ans += 1
                elif L[c] > L[a] + L[b]:
                    break

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import bisect


def main():
    N = int(input())
    L = sorted(map(int, input().split()))
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            ans += bisect.bisect_right(L, L[a] + L[b] - 1) - b - 1

    print(ans)


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

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

from collections import defaultdict
from heapq import *

vs = defaultdict(set)
ws = defaultdict(set)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)

h = []
heappush(h, (0, 1))
cs = {1: 1}
while h:
    l, n = heappop(h)
    if ws[n]:
        for m in ws[n]:
            if not m in cs:
                cs[m] = 1
                heappush(h, (l + 1, m))
    else:
        root = n

h = []

heappush(h, (0, root, 0))

rs = [-1] * (N + 1) 

ls = defaultdict(int)
ls[root] = 0

while h:
    l, n, parent = heappop(h)
    rs[n] = parent
    for m in vs[n]:
        if ls[m] < l + 1:
            heappush(h, (l + 1, m, n))
            ls[m] = l + 1

for i in range(1, N + 1):
    print(rs[i])


### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

import sys
sys.setrecursionlimit(200000)

from collections import defaultdict

vs = defaultdict(set)
ws = defaultdict(set)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)

#print(vs)
#print(ws)

L = []

cs = [0] * (1 + N)

def visit(n):
    if cs[n] == 1:
        return
    elif cs[n] == 0:
        cs[n] = 1
        for m in vs[n]:
            visit(m)
        cs[n] = 2
        L.append(n)

for n in range(1, N + 1):
    if cs[n] == 0:
        visit(n)

#print(L)

nrank = {}

for r, n in enumerate(L):
    nrank[n] = r

#print(nrank)

for n in range(1, N + 1):
    r = 0
    if ws[n]:
        r = sorted(ws[n], key=lambda x:nrank[x])[0]
    print(r)
### BUGGY CODE ###

X = int(input())
if X == 1:
    print(0,-1)
    exit()
for i in range(-1,X//5):
    for j in range(-1,X//5):
        if (i**5) - (j**5) == X:
            print(i,j)
            exit()

### FIXED CODE ###

X = int(input())
for i in range(-500,500):
    for j in range(-500,500):
        if (i**5) - (j**5) == X:
            print(i,j)
            exit()
### BUGGY CODE ###

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

for i in range(N-K+1):
    tree = H[i:i+K]
    ans.append(tree[-1]-tree[0])
print(min(ans))

### FIXED CODE ###

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

for i in range(N-K+1):
    ans.append(H[i+K-1]-H[i])
print(min(ans))
### BUGGY CODE ###

from collections import deque
import heapq

N = int(input())
A = list(map(int, input().split()))
B = A.copy()
heapq.heapify(B)
ans = deque()

for i in range(N - 1):
    ans.append(A.index(heapq.heappop(B)) + 1)

print(" ".join(map(str, list(ans) + [A.index(B[0]) + 1]))) 

### FIXED CODE ###

from collections import deque

N = int(input())
A = list(map(int, input().split()))
A = list(enumerate(A))
A.sort(key = lambda x: x[1])

ans = deque()

for a in A:
    ans.append(a[0] + 1)

print(" ".join(map(str, ans)))
### BUGGY CODE ###


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
    res = 0
    gd=u.all_group_members()
    ns = "".join(s)
    for ld in gd.values():
        black = 0
        white = 0
        for sd in ld:
            if ns[sd]=="#":
                black += 1
            else:
                white += 1
        res += black * white

    print(res)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

h,w=map(int,input().split())
s=[input() for _ in range(h)]
flag = [[0]*w for _ in range(h)]

def dfs(th,tw):
    global flag,h,w,s
    flag[th][tw] = True
    tblack = 0
    twhite = 0
    if s[th][tw] == "#":
        tblack += 1
    else:
        twhite += 1 
    for x,y in ([0,1],[0,-1],[1,0],[-1,0]):
        nth = th + x
        ntw = tw + y
        if nth >= 0 and nth < h and ntw >= 0 and ntw < w:
            if not flag[nth][ntw] and s[th][tw] != s[nth][ntw]:
                ttb,ttw = dfs(nth,ntw)
                tblack += ttb
                twhite += ttw
    return [tblack,twhite]
                
def main():
    global flag,h,w,s
    res = 0
    for i in range(h):
        for j in range(w):
            if not flag[i][j]:
                black,white = dfs(i,j)
                res += black * white 

    return res
print(main())
### BUGGY CODE ###


class UnionFind:
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)
        self.cnt = 0
 
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt
 
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
A = [int(input()) for _ in range(N)]

uf = UnionFind(N+1)
maxims = [A[0]]
ans = 1
for i in range(1,N):
    maxims.sort(reverse = True)
    for j,m in enumerate(maxims):
        if A[i] > m:
            maxims[j] = A[i]
            break
    else:
        maxims.append(A[i])
        ans += 1
    
print(ans)
    
    

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

N = int(input())
A = [-1*int(input()) for _ in range(N)]

maxims = [A[0]]
ans = 1
for a in A[1:]:
    if maxims[-1] > a:
        idx = bisect.bisect(maxims,a)
        maxims[idx] = a
    else:
        maxims.append(a)
        ans += 1
    
print(ans)
### BUGGY CODE ###

n=int(input())
strl=[input() for i in range(n)]

def anagram(sa,sb) :
  flag=True
  sal=list(sa)
  sbl=list(sb)
  for st in sal :
    if st in sbl :
      sbl.remove(st)
    else :
      flag=False
      break
  if flag==False :
    return False
  else:
    return True
   
#print(anagram("peanutbomb","constraint"))    
count=0
for i in range(n) :
  for j in range(n) :
    if i>= j :
      continue
    if anagram(strl[i],strl[j]) ==True :
      count+=1
print(count)

### FIXED CODE ###

#import numpy as np
n=int(input())
strl=[list(input()) for i in range(n)]

count=0
pt={}
#il=np.arange(n)
for i in range(n) :
  sal=strl[i]
  sal.sort()
  temp="".join(sal)
  if temp in pt.keys() :
    #ptがある
    tempc=pt[temp]
    count+=tempc
    pt[temp]=tempc+1
  else :
    pt[temp]=1
print(count)
#print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
l=[[] for i in range(m)]
s=[]
for i in range(n):
   a,b=map(int,input().split())
   if a<=m:
     l[a-1].append(b)

t=0
for i in range(m):
   s += l[i]
   if len(s)>0:
      s.sort(reverse=True)
      t+=s.pop(0)

print(t)


### FIXED CODE ###

import heapq

n,m=map(int,input().split())
l=[[] for i in range(m)]
s=[]
for i in range(n):
   a,b=map(int,input().split())
   if a<=m:
     l[a-1].append(b)

t=0
heapq.heapify(s)

for i in range(m):
  for j in range(len(l[i])):
    heapq.heappush(s,-l[i][j])
  if len(s)>0:
    t-=heapq.heappop(s)

print(t)
### BUGGY CODE ###

s = list(input())

s_split = []
tmp = []
for i in range(len(s) - 1):
    tmp.append(s[i])
    if s[i] == 'L' and s[i + 1] == 'R':
        s_split.append(tmp)
        tmp = []
tmp.append(s[-1])
s_split.append(tmp)

out = ''
for _split in s_split:
    for i in range(len(_split) - 1):
        if _split[i] == 'R' and _split[i + 1] == 'L':
            idx = i

    tmp = [0] * len(_split)
    if len(_split) % 2 == 0:
        tmp[idx] = len(_split) // 2
        tmp[idx + 1] = len(_split) // 2

    else:
        if idx % 2 == 1:
            r_int = (len(_split) - 1) // 2
            l_int = (len(_split) + 1) // 2

        else:
            l_int = (len(_split) - 1) // 2
            r_int = (len(_split) + 1) // 2
        tmp[idx] = r_int
        tmp[idx + 1] = l_int

    for i in range(len(_split)):
        out += ' ' + str(tmp[i])

print(out[1:])


### FIXED CODE ###

s = list(input())

s_split = []
tmp = []
idx_all = []
l = -1
for i in range(len(s) - 1):
    tmp.append(s[i])
    if s[i] == 'R' and s[i + 1] == 'L':
        idx_all.append(i - l - 1)
    if s[i] == 'L' and s[i + 1] == 'R':
        s_split.append(tmp)
        tmp = []
        l = i
tmp.append(s[-1])
s_split.append(tmp)

out = ''
for a in range(len(s_split)):
    idx = idx_all[a]
    _split = s_split[a]

    if len(_split) % 2 == 0:
        r_int = len(_split) // 2
        l_int = len(_split) // 2

    else:
        if idx % 2 == 1:
            r_int = (len(_split) - 1) // 2
            l_int = (len(_split) + 1) // 2

        else:
            l_int = (len(_split) - 1) // 2
            r_int = (len(_split) + 1) // 2

    out += ' 0' * idx
    out += ' ' + str(r_int)
    out += ' ' + str(l_int)
    out += ' 0' * (len(_split) - idx - 2)

print(out[1:])
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())

A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

out=[]

for i in range(X):
    for j in range(Y):
        for k in range(Z):
            out.append(A[i]+B[j]+C[k])

out.sort(reverse=True)

for i in range(K):
    print(out[i])


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
     
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
     
r=[]
out=[]
     
for i in range(X):
    for j in range(Y):
        r.append(A[i]+B[j])
     
r.sort(reverse=True)
     
if len(r)>K:
    for i in range(K):
        for j in range(Z):
            out.append(r[i]+C[j])
else:
    for i in range(len(r)):
        for j in range(Z):
           out.append(r[i]+C[j])
     
out.sort(reverse=True)
     
for i in range(K):
    print(out[i])
### BUGGY CODE ###

S=list(input())
T=list(input())
len0=len(S)
while len(S)<len(T)*2:
    S=S+S

S=S+S

p=26
mod=(1<<50)+1# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

TABLE2=[0]# Rolling Hashのテーブル. 最初は0
LEN2=len(T)

for i in range(LEN2):
    TABLE2.append((p*TABLE2[-1]%mod+ord(T[i])-97)%mod)# テーブルを埋める

TH=TABLE2[-1]

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)

### FIXED CODE ###

S=list(input())
T=list(input())
len0=len(S)
S=S*(len(T)//len0+1)

S=S+S

p=26
mod=(1<<31)+7# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

NOW=0
LEN2=len(T)

for i in range(LEN2):
    NOW=(p*NOW%mod+ord(T[i])-97)%mod

TH=NOW

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)
### BUGGY CODE ###

n,m,l = map(int,input().split())
Edge = [list(map(int,input().split())) for i in range(m)]
q = int(input())
Query = [list(map(int,input().split())) for i in range(q)]

D2 = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    if Edge[i][2] <= l:
        D2[Edge[i][0]-1][Edge[i][1]-1] = Edge[i][2]
        D2[Edge[i][1]-1][Edge[i][0]-1] = Edge[i][2]
for i in range(n):
    D2[i][i] = 0

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

D2 = warshall_floyd(D2)

D = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    if Edge[i][2] <= l:
        D[Edge[i][0]-1][Edge[i][1]-1] = 1
        D[Edge[i][1]-1][Edge[i][0]-1] = 1
for i in range(n):
    D[i][i] = 0
for i in range(n):
    for j in range(n):
        if D2[i][j] <= l:
            D[i][j] = 1

D = warshall_floyd(D)

for query in Query:
    if D[query[0]-1][query[1]-1] != float('inf'):
        print(D[query[0]-1][query[1]-1]-1)
    else:
        print(-1)


### FIXED CODE ###

def main():

    import sys
    input = sys.stdin.readline

    n,m,l = map(int,input().split())
    Edge = [list(map(int,input().split())) for i in range(m)]
    q = int(input())
    Query = [list(map(int,input().split())) for i in range(q)]

    D2 = [[float("inf") for i in range(n)] for i in range(n)]
    for i in range(m):
        D2[Edge[i][0]-1][Edge[i][1]-1] = Edge[i][2]
        D2[Edge[i][1]-1][Edge[i][0]-1] = Edge[i][2]
    for i in range(n):
        D2[i][i] = 0

    def warshall_floyd(d):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        return d

    D2 = warshall_floyd(D2)

    D = [[float("inf") for i in range(n)] for i in range(n)]
    for i in range(m):
        if Edge[i][2] <= l:
            D[Edge[i][0]-1][Edge[i][1]-1] = 1
            D[Edge[i][1]-1][Edge[i][0]-1] = 1
    for i in range(n):
        D[i][i] = 0
    for i in range(n):
        for j in range(n):
            if D2[i][j] <= l:
                D[i][j] = 1

    D = warshall_floyd(D)

    for query in Query:
        if D[query[0]-1][query[1]-1] != float('inf'):
            print(D[query[0]-1][query[1]-1]-1)
        else:
            print(-1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
import sys
sys.setrecursionlimit(2000)

H, W = [int(x) for x in input().split()]
s = [list(input()) for i in range(H)]
M = np.array([[ (0 if s[i][j] == '.' else 1) for j in range(W) ] for i in range(H)])

def solve(M):

    Mr = np.copy(M)
    Mc = np.copy(M)


    H = M.shape[0]
    W = M.shape[1]

    ret = 0

    if M.sum() == 0:
        return ret
    elif H == W == 1:
        return M[0][0]


    del_row = 100000
    del_col = 100000
    retr = 0
    retc = 0
    if H > 1:
        if Mr[0][0] == 1:
            h = 1
            w = 1
            while h < H and M[:h + 1, :w].sum() == (h + 1) * w:
                h += 1
            while w < W and M[:h, :w + 1].sum() == h * (w + 1):
                w += 1

            for i in range(h):
                for j in range(w):
                    Mr[i][j] = 0
            retr += 1

        del_row = solve(Mr[1:, :])


    if W > 1:

        if Mc[0][0] == 1:

            h = 1
            w = 1

            while w < W and Mc[:h, :w + 1].sum() == h * (w + 1):
                w += 1
            while h < H and Mc[:h + 1, :w].sum() == (h + 1) * w:
                h += 1


            for i in range(h):
                for j in range(w):
                    Mc[i][j] = 0
            retc += 1

        del_col = solve(Mc[:, 1:])

    return min(retr + del_row, retc + del_col)


print(solve(M))


### FIXED CODE ###

import numpy as np

H, W = [int(x) for x in input().split()]
s = [list(input()) for i in range(H)]

M = np.array([[ (0 if s[i][j] == '.' else 1) for j in range(W) ] for i in range(H)])
INF = 10 ** 9
dp = np.array([[INF for j in range(W)] for i in range(H)])

for i in range(H - 1, -1, -1):
    for j in range(W - 1, -1, -1):
        ans_r = INF
        ans_d = INF
        if i == H - 1 and j == W - 1:
            dp[i][j] = M[i][j]
            continue
        if j < W - 1:  # 右に動ける
            if M[i][j] == 1 and M[i][j + 1] == 0:
                ans_r = dp[i][j + 1] + 1
            else:
                ans_r = dp[i][j + 1]
        if i < H - 1:  # 下に動ける
            if M[i][j] == 1 and M[i + 1][j] == 0:
                ans_d = dp[i + 1][j] + 1
            else:
                ans_d = dp[i + 1][j]
        dp[i][j] = min(ans_r, ans_d)

print(dp[0][0])
### BUGGY CODE ###

n = int(input())
a = [int(k) for k in input().split()]
b=0
for j in range(n):
    for k in range(n):
        if a[j]==a[k] and j!=k:
            b+=1
            break
if b==0:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

import sys
import math
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n = i()
a = intl()
a = list(set(a))
if len(a) == n:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h=sorted(h)
s=[]
for i in range(n-1):
    s.append(h[i+1]-h[i])

ans=10**10
for i in range(n-k+1):
    p=sum(s[i:i+k-1])
    ans=min(ans,p)

print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
h=sorted(int(input()) for i in range(n))
ans=10**10
for i in range(n-k+1):
    ans=min(h[i+k-1]-h[i],ans)
print(ans)