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

import queue
import sys
sys.setrecursionlimit(1000000)

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

que = queue.Queue()
class stgo:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.depth = 0
y_dist = (0, 0, -1, +1)
x_dist = (-1, +1, 0, 0)
g_y = 0
g_x = 0

def bfs():
    dist = [[-1] * (w) for i in range(h)]
    maxdepth = 0
    while not que.empty():
        now = que.get()
        y = now.y
        x = now.x
        depth = now.depth
        dist[now.y][now.x] = depth
        maxdepth = max(maxdepth, depth)

        for z in range(4):
            next = stgo()
            next.y = y + y_dist[z]
            next.x = x + x_dist[z]
            next.depth = depth + 1

            if next.y >= 0 and next.y <= h - 1 and next.x >= 0 and next.x <= w - 1 and s[next.y][next.x] == "." and dist[next.y][next.x] == -1:
                que.put(next)
    return maxdepth

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            start = stgo()
            start.x = j
            start.y = i
            start.depth = 0
            que.put(start)
            ans = max(ans,bfs())
print(ans)


### FIXED CODE ###

import queue

H, W = map(int, input().split())
S = [input() for i in range(H)]
q = queue.Queue()
longest_path = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            g = [[0 if S[k][l] == '.' else -1 for l in range(W)] for k in range(H)]
            q.put((i,j))
            g[i][j] = 0
            while not(q.empty()):
                x, y = q.get()
                for nx, ny in [(x+1, y),(x-1, y),(x, y+1),(x, y-1)]:
                    if nx < 0 or nx > H-1 or ny < 0 or ny > W-1: continue
                    if g[nx][ny] != 0: continue
                    if nx == i and ny == j: continue
                    g[nx][ny] = g[x][y] + 1
                    q.put((nx,ny))
            longest_path = max(longest_path, max(map(max, g)))
print(longest_path)
### BUGGY CODE ###

x = int(input())
a = int(x**0.2)
b = 0
while a**5 - b**5 != x:
    b -= 1
print(a, b)


### FIXED CODE ###

x = int(input())
for a in range(-1000, 1000):
    for b in range(-1000, 1000):
        if a**5 - b**5 == x:
            print(a, b)
            quit()
### BUGGY CODE ###

s = input()
q = int(input())

rev = 0

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        rev += 1
    else:
        if (t[1] == "1" and rev % 2 == 0) or (t[1] == "2" and rev % 2 != 0):
            s = t[2] + s
        else:
            s += t[2]

if rev % 2 == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

rev = False

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        rev = not rev
    else:
        if t[1] == "1":
            s.append(t[2]) if rev else s.appendleft(t[2])
        else:
            s.appendleft(t[2]) if rev else s.append(t[2])

if rev:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

N = int(input())
S = input()

ans = N+1
for i in range(N):
    ans = min(ans,S[:i].count("W") + S[i+1:].count("E"))

print(ans)


### FIXED CODE ###

N = int(input())
S = input()

# 案の定TLE
# ans = N+1
# for i in range(N):
#     ans = min(ans,S[:i].count("W") + S[i+1:].count("E"))

left = 0
right = S.count("E")
ans = N+1
for i in range(N):
    if S[i] == "E":
        right -= 1
    ans = min(ans,left + right)
    if S[i] == "W":
        left += 1

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

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n

for i in range(1,n):
    dp[i] = min([dp[j] + abs(h[i]-h[j]) for j in range(max(0,i-k),i)])
print(dp[n-1])


### FIXED CODE ###

def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[0]*n

    for i in range(1,n):
        dp[i] = min([dp[j] + abs(h[i]-h[j]) for j in range(max(0,i-k),i)])
    print(dp[n-1])

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

n=int(input())
s=input()
L=len(s)
ans=0
R=[]
G=[]
B=[]
for i in range(L):
    if s[i]=='R':
        R.append(i)
    elif s[i]=='G':
        G.append(i)
    else:
        B.append(i)
for r in R:
    for g in G:
        for b in B:
            X=[r,b,g]
            X.sort()
            if X[1]-X[0]==X[2]-X[1]:
                continue
            ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
L=len(s)
ans=0

r=s.count('R')
b=s.count('B')
g=s.count('G')

for i in range(L-2):
    for j in range(i+1,L-1):
        if s[j]!=s[i]:
            if j+j-i<=L-1:
                if s[j+j-i]!=s[i] and s[j+j-i]!=s[j]:
                    ans+=1
print(r*b*g-ans)
### BUGGY CODE ###

n, q = list(map(int, input().split(' ')))
splice = [[] for i in range(n)]

for i in range(q):
    query, *val = list(map(int, input().split(' ')))
    if query == 0:
        t, x = val
        splice[t].append(x)
    elif query == 1:
        t = val[0]
        print(' '.join(list(map(str, splice[t]))))
    else:
        s, t = val
        splice[t].extend(splice[s])
        splice[s] = []


### FIXED CODE ###

class Node:
    def __init__(self, val=None, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

class DoublyLinkedList():
    def __init__(self):
        self.start = Node(val='START', prev=None, next=None)
        self.end = Node(val='END', prev=self.start, next=None)
        self.start.next = self.end

    def insert(self, x):
        new_node = Node(val=x, prev=self.end.prev, next=self.end)
        self.end.prev.next = new_node
        self.end.prev = new_node

    def dump(self):
        node_list = []
        crnode = self.start.next
        while crnode != self.end:
            node_list.append(crnode.val)
            crnode = crnode.next
        print(' '.join(list(map(str, node_list))))

    def extend(self, dll):
        self.end.prev.next = dll.start.next
        dll.start.next.prev = self.end.prev
        self.end = dll.end

n, q = list(map(int, input().split(' ')))
splice = [DoublyLinkedList() for i in range(n)]

for i in range(q):
    op, *val = list(map(int, input().split(' ')))
    if op == 0:
        splice[val[0]].insert(val[1])
    elif op == 1:
        splice[val[0]].dump()
    else:
        splice[val[1]].extend(splice[val[0]])
        splice[val[0]] = DoublyLinkedList()
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N,M = map(int,readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1<<(int(x)-1) for  x in readline().split()))

INF = 10**18
dp = [INF] * (1<<N)
dp[0] = 0

for n in range(1<<N):
    for (a,b),c in zip(AB,C):
        m = n|c
        dp[m] = min(dp[m],dp[n]+a)

answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N,M = map(int,readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1<<(int(x)-1) for  x in readline().split()))

INF = 10**18
dp = [INF] * (1<<N)
dp[0] = 0

for n in range(1<<N):
    for (a,b),c in zip(AB,C):
        m = n|c
        dp[m] = min(dp[m],dp[n]+a)

answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
	l, r = map(int, input().split())
	print(S.count("AC", l - 1, r))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
li = [0 for _ in range(N + 1)]
for i in range(N):
	li[i + 1] = li[i] + (1 if S[i:i+2] == 'AC' else 0)
for _ in range(Q):
	l, r = map(int, input().split())
	print(li[r - 1] - li[l - 1])
### BUGGY CODE ###

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

ss = []
cnt = 0
for i in range(N):
    x = list(s[i])
    x.sort()
    y = "".join(x)
    cnt += ss.count(y)
    ss.append(y)

print(cnt)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for i in range(N)]
 
ctr = Counter()
ans = 0
for s in S:
    a = ''.join(sorted(list(s)))
    if a in ctr:
        ans += ctr[a]
    ctr[a] += 1
print(ans)
### BUGGY CODE ###

import sys
X = int(input())

for i in range(X+1):
    for j in range(X):
        if i ** 5 - j ** 5 == X:
            print(i,j)
            sys.exit()
        elif i ** 5 - (-j) ** 5 == X:
            print(i,-j)
            sys.exit()


### FIXED CODE ###

import sys
X = int(input())
# for i in range(1000):
#     for j in range(1000):
#         a = i ** 2
#         b = j ** 2
#         c = i * j
#         if (i - j) * (a * (a ** 2 + c + b) + b * (c + b)) == X:
#             print(i,j)
#             sys.exit()
#         elif (i + j) * (a * (a ** 2 - c + b) + b * (-c + b)) == X:
#             print(i,-j)
#             sys.exit()

for i in range(-118,120):
    for j in range(-118,120):
        if i ** 5 - j ** 5 == X:
            print(i,j)
            sys.exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0 = list(map(lambda x:x[1], ab0))
abn = list(map(lambda x:x[0], abn))


res="IMPOSSIBLE"
for x in ab0:
    if x in abn:
        res= "POSSIBLE"
        break
 
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0_bin = ["0"]*n
abn_bin = ["0"]*n
for x in ab0:
    ab0_bin[x[1]] = "1"
for x in abn:
    abn_bin[x[0]] = "1"

ab0_bin = "".join(ab0_bin)
abn_bin = "".join(abn_bin)

if bin(int(ab0_bin,2) & int(abn_bin, 2))[2:].count("1") > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

#!/usr/bin/env python3
N,K,Q=(int(x) for x in input().split())
a=[int(input()) for i in range(Q)]#正解者
l=[]
for j in range(N):
    l.append(K)
for k in range(Q):
    for m in range(N):
        l[m]-=1
        if m+1==a[k]:
            l[m]+=1
for n in range(N):
    if(l[n]>=1):
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

#!/usr/bin/env python3
N,K,Q=(int(x) for x in input().split())
a=[int(input()) for i in range(Q)]#正解者
l=[]
for j in range(N):
    l.append(K-Q)
for k in range(Q):
  l[a[k]-1]+=1

for n in range(N):
    if(l[n]>=1):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
arrA = list(map(int,input().split()))

ctA = Counter(arrA)
dp = {}
for i in arrA:
    if i in dp:
        print(dp[i])
        continue
    ctA[i] -= 1
    temp = 0
    for k,v in ctA.items():
        if v>1:
            temp += v*(v-1)//2
    print(temp)
    dp[i] = temp
    ctA[i] += 1

# print(*ans,sep="\n")
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する



### FIXED CODE ###

# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
arrA = list(map(int,input().split()))

cbdp = [0,0]
cbdp2 = [i*(i-1)//2 for i in range(2,n+1)]
cbdp += cbdp2
# print(cbdp)

ctA = Counter(arrA)
# print(ctA)

totalconb = 0
for v in ctA.values():
    totalconb += cbdp[v]
# print(totalconb)

for a in arrA:
    print(totalconb-cbdp[ctA[a]]+cbdp[ctA[a]-1])

# print(*ans,sep="\n")
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
### BUGGY CODE ###

K = int(input())

for i in range(1,10 ** 6):
    x = int('7' * i)
    if x % K == 0:
        print(i)
        exit()
print(-1)

### FIXED CODE ###

K = int(input())
mod = K
num = 0
for i in range(10 ** 6):
    num += 7 * pow(10, i, mod)
    num %= mod
    if num == 0:
        print(i + 1)
        exit()
print(-1)
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
count=0
l=[]
for i in range(1,N):
    num = 0
    for j in range(i):
        if P[i]<=P[j]:
            num+=1
        else:
            continue
    if num==i:
        l.append(l)
print(len(l)+1)


### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
count=0
min=2*10**5
for i in range(N):
    if P[i]<=min:
        min=P[i]
        count+=1
print(count)
### BUGGY CODE ###

N = int(input())
A = [input() for _ in range(N)]
tmp = 0
for i in range(N):
    if max(A) == A[i]:
        tmp = A.pop(i)
        print(max(A))
        A.insert(i,tmp)
    else:
        print(max(A))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
if N == 2:
    for j in A[::-1]:
        print(j)
else:
    tmp = sorted(A)
    del tmp[0:(N-2)]
    for i in range(N):
        if A[i] == tmp[1]:
            print(tmp[0])
        else:
            print(tmp[1])
### BUGGY CODE ###

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

B = [(A[i], i) for i in range(N)]
B.sort(key = lambda x: x[0], reverse = True)

DP = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    a = B[i][0]
    tmp = B[i][1]
    for x in range(i + 1):
        DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
        DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

ans = 0
for i in range(N + 1):
    ans = max(ans, DP[i][N - i])

print (ans)

# for tmp in DP:
#     print (tmp)

### FIXED CODE ###

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

B = [(A[i], i) for i in range(N)]
B.sort(key = lambda x: x[0], reverse = True)

DP = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    a = B[i][0]
    tmp = B[i][1]
    for x in range(i + 1):
        DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
        DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

ans = 0
for i in range(N + 1):
    ans = max(ans, DP[i][N - i])

print (ans)

# for tmp in DP:
#     print (tmp)
### BUGGY CODE ###

while True:
    try:
        n = int(raw_input())
        count = 0
        for a in range(1000,-1,-1):
            if 0 <= n - a <= 3000:
                for b in range(1000,-1,-1):
                    if 0 <= n - a - b <= 1000:
                        count += n-a-b+1
                    elif 1001 < n - a - b <= 2000:
                        count += (2000 - (n-a-b) + 1)
        print count
    except:
        break

### FIXED CODE ###

import sys
def N(n):
    return (n+1)*(n+2)*(n+3)/6
for n in sys.stdin:
    n = int(n)
    if n > 2000:
        n = 4000 - n
    if n < 1001:
        print N(n)
    else:
        m = n - 1000
        print N(n) - (N(2*m) - m - 1)/2
### BUGGY CODE ###

#094c
import copy
N = int(input()) #N<200000=2 * 10**5
X_list = [int(e) for e in input().split()]
#print(X_list)

for i in range(N):
    copy_X_list = copy.copy(X_list)
    copy_X_list.pop(i)
    copy_X_list.sort(reverse=False)
    #print(copy_X_list)
    print(copy_X_list[int(len(X_list)/2) -1])

### FIXED CODE ###

#094c
import copy
N = int(input()) #N<200000=2 * 10**5
X_list = [int(e) for e in input().split()]

sort_X_list = copy.copy(X_list)
sort_X_list.sort(reverse=False)
Bi_smaller = sort_X_list[int(len(X_list)/2-1)]
Bi_bigger = sort_X_list[int(len(X_list)/2)]

for i in range(N):
    if X_list[i]>=Bi_bigger:
        print(Bi_smaller)
    else:
        print(Bi_bigger)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
int_list = []
for _ in range(N):
    A, B = map(int, input().split())
    int_list.append([A, B])

K_bin = bin(K)[2:]
max_len = len(K_bin)
for i in range(N):
    int_list[i] = (bin(int_list[i][0])[2:].zfill(max_len), int_list[i][1])

or_list = [K_bin]
for i in range(max_len):
    if K_bin[i] == '1':
        or_list.append(K_bin[:i] + '0' + '1' * (max_len - i - 1))

ans = 0
for k in or_list:
    ans_k = 0
    for A, B in int_list:
        if len(A) > max_len:
            continue
        ok = 1
        for j, a in enumerate(A):
            if a == '1' and k[j] == '0':
                ok = 0
        if ok:
            ans_k += B
    ans = max(ans, ans_k)

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
int_list = []
for _ in range(N):
    A, B = map(int, input().split())
    int_list.append([A, B])

K_bin = bin(K)[2:]
max_len = len(K_bin)
for i in range(N):
    int_list[i] = (bin(int_list[i][0])[2:].zfill(max_len), int_list[i][1])

or_list = [K_bin]
for i in range(max_len):
    if K_bin[i] == '1':
        or_list.append(K_bin[:i] + '0' + '1' * (max_len - i - 1))

ans = 0
for k in or_list:
    ans_k = 0
    for A, B in int_list:
        if len(A) > max_len:
            continue
        ok = 1
        for j, a in enumerate(A):
            if a == '1' and k[j] == '0':
                ok = 0
                break
        if ok:
            ans_k += B
    ans = max(ans, ans_k)

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

n = int(input())
p = list(map(int,input().split()))
count = 0
for x in range(len(p)):
  if p[x] == min(p[:x+1]):
    count += 1

print(count)
    

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 0
a = p[0]
for x in range(len(p)):
  if p[x] <= a:
    count += 1
    a = p[x]
  
print(count)
### BUGGY CODE ###

import math
import numpy as np

N,M = map(int,input().split())
A = np.array(list(map(int, input().split())))

def discount(price):
    return math.floor(price / 2)

for i in range(M):
    A[np.argmax(A)] = discount(A[np.argmax(A)])

print(np.sum(A))

### FIXED CODE ###

import heapq as hq
import math

def discount(price):
    return math.ceil(price / 2)

N,M = map(int,input().split())
A = list(map(lambda x: int(x)* -1,input().split()))
hq.heapify(A)

for _ in range(M):
    a = discount(hq.heappop(A))
    hq.heappush(A,a)

print(sum(A)* -1)
### BUGGY CODE ###

k = int(input())
s = input()
mod = 10 ** 9 + 7

MAX = 2 * 10 ** 6

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


ln = len(s)

ans = 0
pow25 = 1
pow26 = pow(26, k, mod)
inv26 = pow(26, mod - 2, mod)
for i in range(ln, k + ln + 1):
    ans += pow25 * pow26 * comb(i - 1, ln - 1)
    ans %= mod
    pow25 *= 25
    pow25 %= mod
    pow26 *= inv26
    pow26 %= mod

print(ans)


### FIXED CODE ###

k = int(input())
s = input()
mod = 10 ** 9 + 7

MAX = 2 * 10 ** 6

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


ln = len(s)

ans = 0
pow25 = 1
pow26 = pow(26, k, mod)
inv26 = pow(26, mod - 2, mod)
for i in range(ln, k + ln + 1):
    ans += pow25 * pow26 % mod * comb(i - 1, ln - 1) % mod
    ans %= mod
    pow25 *= 25
    pow25 %= mod
    pow26 *= inv26
    pow26 %= mod

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

from collections import deque

H, W = list(map(int, input().split()))


masu = [input() for _ in range(H)]

# search for kuro
kuro = 0
for row in masu:
    for s in row:
        if s == '#':
            kuro += 1


# search for minimum dist by bfs
que = deque([(0, 0, 0)])
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[False for _ in range(W)] for _ in range(H)]

# print(len(visited[0]), len(visited))

while (que):
    i, j, cost = que.popleft()
    visited[j][i] = True
    if (j == H - 1) and (i == W - 1):
        break

    for movex, movey in move:
        tmpx, tmpy = i + movex, j + movey
        if (tmpx < 0) or(tmpx >= W) or (tmpy < 0) or (tmpy >= H):
            continue

        if (masu[tmpy][tmpx] == '.') and not(visited[tmpy][tmpx]):
            que.append((i + movex, j + movey, cost + 1))
else:
    print(-1)
    exit()

print(H * W - kuro - cost - 1)


### FIXED CODE ###

from collections import deque

H, W = list(map(int, input().split()))


masu = [input() for _ in range(H)]

# search for kuro
kuro = 0
for row in masu:
    for s in row:
        if s == '#':
            kuro += 1


# search for minimum dist by bfs
que = deque([(0, 0, 0)])
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[False for _ in range(W)] for _ in range(H)]

# print(len(visited[0]), len(visited))

while (que):
    i, j, cost = que.popleft()
    # print(i, j)

    visited[j][i] = True
    if (j == H - 1) and (i == W - 1):
        break
    for movex, movey in move:
        tmpx, tmpy = i + movex, j + movey
        # visited[tmpy][tmpx] = True

        # if (tmpx < 0) or(tmpx >= W) or (tmpy < 0) or (tmpy >= H):
        if not(tmpx in range(W)) or not(tmpy in range(H)):
            continue

        if (masu[tmpy][tmpx] == '.') and not(visited[tmpy][tmpx]):
            que.append((i + movex, j + movey, cost + 1))
            visited[tmpy][tmpx] = True
else:
    print(-1)
    exit()
# print(sum(visited[4]))
print(H * W - kuro - cost - 1)
### BUGGY CODE ###

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

real_ans=0
ans1=list(set(A))
for k in range(len(ans1)):
    num_k=A.count(ans1[k])
    real_ans+=(num_k*(num_k-1))//2

for i in range(N):
    num=A.count(A[i])
    re_ans=real_ans-(num-1)
    print(re_ans)

### FIXED CODE ###

import collections

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

ans=0
dic=collections.Counter(A)
keys=list(dic.keys())
values=list(dic.values())


for i in values:
    
    ans+=(i*(i-1))//2

for j in A:
    ANS=ans
    num=dic[j]
    ANS=ANS-(num-1)
    print(ANS)
### BUGGY CODE ###

N=int(input())
P=1
for i in range(N):
   P=P*(i+1)
   M=P%(10**9+7)

print(M)

### FIXED CODE ###

N=int(input())
P=1
for i in range(N):
   P=P*(i+1)
   P=P%(10**9+7)

print(P)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
C = list(set(A))
B = [0 for i in range(len(C))]
for a in A:
    B[C.index(a)] += 1
#B = list(sorted([A.count(b) for b in set(A)], reverse=True))
B = list(sorted(B, reverse=True))
print(sum(B[K:len(B)]))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = {i:0 for i in set(A)}
for a in A:
    B[a] += 1
print(sum(sorted(B.values())[:-K]))