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

from collections import defaultdict

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

count_dict = defaultdict(int)
for cal in A:
  count_dict[cal] += 1
    
    
"""
それぞれの要素について、1個減った時とそのままの場合での組み合わせ数を事前に計算しておく
"""

from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))
  
# list[0]=そのまま、list[1]=1個減った場合
count_result = defaultdict(list)
for k,v in count_dict.items():
  if v > 2:
    count_result[k] = [combinations_count(v,2), combinations_count(v-1,2)]
  elif v == 2:
    count_result[k] = [1,0]    
  else:
    count_result[k] = [0,0]
    

"""
前から順に表示していく
"""

for _ in A:
  # 対象の数字
  ans = 0
  for k,v in count_result.items():
    if k == _:
      ans += v[1]
    else:
      ans += v[0]

  print(ans)



### FIXED CODE ###

from collections import defaultdict

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

count_dict = defaultdict(int)
for cal in A:
  count_dict[cal] += 1
    
from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

count_result = defaultdict(list)
for k,v in count_dict.items():
  if v > 2:
    count_result[k] = [combinations_count(v,2), combinations_count(v-1,2)]
  elif v == 2:
    count_result[k] = [1,0]    
  else:
    count_result[k] = [0,0]

all_ans = 0
for v in count_result.values():
  all_ans += v[0]


for _ in A:
  ans = all_ans - count_result[_][0] + count_result[_][1]
  print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
x,y,z,k = map(int,input().split())
a,b,c = [],[],[]
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []

for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])

ab.sort()

abc = []

for i in range(min(len(ab),k)):
    for j in range(min(z,k)):
        abc.append(ab[-(i+1)] + c[j])

abc.sort()

for i in range(k):
    print(abc[-(i+1)])

### FIXED CODE ###

# -*- coding: utf-8 -*-
x,y,z,k = map(int,input().split())
a,b,c = [],[],[]
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []

for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])

ab.sort()

abc = []

for i in range(min(len(ab),k)):
    for j in range(min(z,k)):
        abc.append(ab[-(i+1)] + c[j])

abc.sort()

for i in range(k):
    print(abc[-(i+1)])
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))

INF=float('inf')
dp=[INF]*N
dp[0]=0

for i in range(N):
  for j in range(K+1):
    if i+j<len(h):
      dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
      
print(dp[N-1])


### FIXED CODE ###

N,K = map(int, input().split())
H = list(map(int, input().split()))
 
inf = 10**4*N
dp = [inf]*N
dp[0] = 0
for i,h in enumerate(H):
    if i == 0:
        continue
    m = max(0, i-K)
    dp[i] = min([dpj + abs(h - hj) for dpj, hj in zip(dp[m:i], H[m:i])])
print(dp[N-1])
### BUGGY CODE ###

S = list(input())
n = int(input())
Q = [list(map(str, input().split())) for _ in range(n)]
cnt = 0
for q in Q:
    if q[0] == "1":
        cnt += 1
#         S.reverse()
    elif q[0] == "2":
        if (int(q[1])+cnt)%2 == 1:
            S.insert(0,q[2])
        else:
            S.append(q[2])

if cnt%2==1:
    S.reverse()
print("".join(S))

### FIXED CODE ###

S = str(input())
n = int(input())
Q = [list(map(str, input().split())) for _ in range(n)]
cnt = 0
s_pre = ""
s_pro = ""
for q in Q:
    if q[0] == "1":
        cnt += 1
    else:
        if (int(q[1])+cnt)%2 == 1:
#             S = q[2] + S
            s_pre = q[2] + s_pre
        else:
            s_pro = s_pro + q[2]
#             S = S + q[2]

S = s_pre + S + s_pro
if cnt%2==1:
    S = list(S)
    S.reverse()
print("".join(S))
### BUGGY CODE ###

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

for i in range(N):
    A[i] = (A[i]+1)/2

t = 0
for i in range(K):
    t += A[i]
L = (t,)

ans = 0

for i in range(N-K):
    L  = L + (L[i]+A[K+i]-A[i],)
    ans = max(ans, L[i+1])
print(max(L))

### FIXED CODE ###

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

L = 0
for i in range(K):
    L += A[i]

ans = L

for i in range(N-K):
    L  = L+A[K+i]-A[i]
    ans = max(ans, L)
ans += K
ans /= 2
print(ans)
### BUGGY CODE ###

mod = 10 ** 9 + 7
S = input()
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'C':
        c = ((3 ** q) % mod + c) % mod
    if i == 'B':
        bc = (bc + c) % mod
    if i == 'A':
        abc = (abc + bc) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (c * 3 + (3 ** q) %mod) % mod
        q += 1
        
print(abc)

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'A':
        abc = (bc + abc) % mod
    if i == 'B':
        bc = (c + bc) % mod
    if i == 'C':
        c = (pow(3, q, mod) + c ) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (pow(3, q, mod) + c * 3) % mod
        q += 1
        
print(int(abc))
### BUGGY CODE ###

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

for i in range(N-2):
    for j in range(i+1, N-1):
        a = L[i]
        b = L[j]
        ok = j
        ng = N-1
        if b-a < L[ng] and L[ng] < a+b:
            ans += N-1-j
        else:
            while ng - ok > 1:
                mid = (ok+ng) // 2
                if b-a < L[mid] and L[mid] < a+b:
                    ok = mid
                else:
                    ng = mid
       
            ans += ok - j

print(ans)

### FIXED CODE ###

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

for i in range(N-2):
    for j in range(i+1, N-1):
        a = L[i]
        b = L[j]
        ok = j
        ng = N-1
        if b-a < L[ng] and L[ng] < a+b:
            ans += N-1-j
        else:
            while ng - ok > 1:
                mid = (ok+ng) // 2
                if b-a < L[mid] and L[mid] < a+b:
                    ok = mid
                else:
                    ng = mid
       
            ans += ok - j

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

K, S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k ==S:
                cnt += 1

print(cnt)

### FIXED CODE ###

K,S = map(int,input().split())
a = 0
 
for y in range(K + 1):
     for z in range(K + 1):
        if 0 <= S - y - z <= K:
            a += 1
print(a)
### BUGGY CODE ###

N = int(input())
S = input()
R = 0
G = 0
B = 0
for i in range(N):
    s = S[i]
    if s == "R":
        R += 1
    elif s == "G":
        G += 1
    elif s == "B":
        B += 1
ans = R * G * B
for i in range(N-2):
    for j in range(i+1,N-1):
        k = 2*j - i
        if k <= N-1 and (S[i] != S[j] and S[j] != S[k] and S[k] != S[i]):
            ans -= 1

print(ans)

### FIXED CODE ###

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

R = [0] * N
G = [0] * N
B = [0] * N
SR = [0] * N
SG = [0] * N
SB = [0] * N
pr = 0
pg = 0
pb = 0
for i in range(N):
    if S[i] == "R":
        pr += 1
        SR[i] = pr
        R[i] = 1
    elif S[i] == "G":
        pg += 1
        SG[i] = pg
        G[i] = 1
    elif S[i] == "B":
        pb += 1
        SB[i] = pb
        B[i] = 1
        
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if R[i]:
            if G[j]:
                if j+(j-i) <= N-1 and B[j + (j-i)] == 1:
                    ans += SB[N-1] - SB[j] - 1
                else:
                    ans += SB[N-1] - SB[j]
            if B[j]:
                if j+(j-i) <= N-1 and G[j + (j-i)] == 1:
                    ans += SG[N-1] - SG[j] - 1
                else:
                    ans += SG[N-1] - SG[j]
        if G[i]:
            if B[j]:
                if j+(j-i) <= N-1 and R[j + (j-i)] == 1:
                    ans += SR[N-1] - SR[j] - 1
                else:
                    ans += SR[N-1] - SR[j]
            if R[j]:
                if j+(j-i) <= N-1 and B[j + (j-i)] == 1:
                    ans += SB[N-1] - SB[j] - 1
                else:
                    ans += SB[N-1] - SB[j]
        if B[i]:
            if G[j]:
                if j+(j-i) <= N-1 and R[j + (j-i)] == 1:
                    ans += SR[N-1] - SR[j] - 1
                else:
                    ans += SR[N-1] - SR[j]
            if R[j]:
                if j+(j-i) <= N-1 and G[j + (j-i)] == 1:
                    ans += SG[N-1] - SG[j] - 1
                else:
                    ans += SG[N-1] - SG[j]
print(ans)
### BUGGY CODE ###

# for j in range(1, 11):

n = int(input())
# n = j
ans = n
pay = []
for i in range(1, 10):
    if 6 ** i <= 100000:
        pay.append(6 ** i)
    if 9 ** i <= 100000:
        pay.append(9 ** i)
pay.sort(reverse=True)


def func(n, times):
    for i in pay:
        n2 = n
        times2 = times
        if i <= n:
            global ans
            n2 -= i
            times2 += 1
            if ans > times2 + n2:
                ans = times2 + n2
            if n2 >= 6 and times2 < ans:
                func(n2, times2)


func(n, 0)
print(ans)


### FIXED CODE ###

n = int(input())
ans = [n]
pay = []
for i in range(1, 10):
    if 6 ** i < 100000:
        pay.append(6 ** i)
    if 9 ** i < 100000:
        pay.append(9 ** i)
pay.sort(reverse=True)

def func(n, times):
    for i in range(len(pay)):
        n2 = n
        times2 = times
        if pay[i] <= n2:
            n2 -= pay[i]
            times2 += 1
            if ans[0] > times2 + n2:
                ans[0] = times2 + n2
            if n2 >= 6 and times2 < ans[0]:
                func(n2, times2)
            if n2 > pay[i]*2:
                break


func(n, 0)
print(ans[0])
### BUGGY CODE ###

s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=int(s[-1])

for i in range(1,l+1):
    nd=int(s[l-i-1])
    d=(nd*10**len(str(d)) + d)
    amari[d%2019]+=1

ans=0
for i in amari:
    ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=0
digi=1

for c in s[::-1]:
    d=(int(c)*digi + d)%2019
    amari[d]+=1
    digi=(digi*10)%2019

ans=0
for i in amari:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(50000)

tree = {}
colors = set()
N = 0

def assign(assignment, u, prev_color):
    rest_colors = colors - {prev_color}
    for v, color in zip(tree[u], rest_colors):
        assignment[u,v] = color
        assign(assignment, v, color)

def main():
    global tree, colors, N
    N = int(input())
    colors = set(range(1, N))
    tree = {i: [] for i in range(1,N+1)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        edges.append((a, b))
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

tree = {}
N = 0

def assign(assignment, u, prev_color):
    color = 1
    for v in tree[u]:
        if color == prev_color:
            color += 1
        assignment[u,v] = color
        assign(assignment, v, color)
        color += 1

def main():
    global tree, N
    N = int(input())
    tree = {i: [] for i in range(1,N+1)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        edges.append((a, b))
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

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

a, b, n = map(int, input().split())

ans = 0
zero_cnt = 0
for i in range(n+1):
    tmp = int(a*i/b) - a*int(i/b)
    if ans != 0 and tmp == 0:
        break
    ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
x = min(b-1, n)
print(int(a*x/b))
### BUGGY CODE ###

N, M = [int(c) for c in input().split()]

shops = []
for _ in range(N):
    ab = [int(c) for c in input().split()]
    shops.append(ab)

cost = 0
bought = 0
for i in range(N):
    if i < N - 1:
        target = shops[i][0]
        min_i = i
        for j in range(i+1, N):
            if shops[j][0] < shops[min_i][0]:
                min_i = j
        shops[min_i], shops[i] = shops[i], shops[min_i]

    k = 0
    while k < shops[i][1]:
        if bought == M:
            break
        cost += shops[i][0]
        k += 1
        bought += 1

    if bought == M:
        break

print(cost)

### FIXED CODE ###

N, M = [int(c) for c in input().split()]

shops = []
for _ in range(N):
    ab = [int(c) for c in input().split()]
    shops.append(ab)

cost = 0
bought = 0
s_shops = sorted(shops)

for shop in s_shops:
    buying = 0
    while buying < shop[1]:
        if bought == M:
            break
        cost += shop[0]
        buying += 1
        bought += 1

    if bought == M:
        break

print(cost)
### BUGGY CODE ###

import math
N = int(input())
count = 0
flag = False
n = int(math.sqrt(N)) 
for i in range(1, N + 1):
    
    for j in range(1, n):
        for l in range(1, n):
            for r in range(1, n):
                if j ** 2 + l ** 2 + r ** 2 + j * l + j * r + l * r == i:
                    if j == l == r:
                        flag = True
                        count = 1
                        break
                    else:
                        flag = True
                        count = 3
                        break
            if flag:
                break
        if flag:
            break            
    print(count)
    count = 0
    flag = False

### FIXED CODE ###

# # import math
N = int(input())
# # count = 0
# # flag = False
# # # n = int(math.sqrt(N))
n = 105

# # for i in range(1, N + 1):
    
# #     for j in range(1, n):
# #         for l in range(1, n):
# #             for r in range(1, n):
# #                 if j + l + r > N // 2:
# #                     continue
# #                 if j ** 2 + l ** 2 + r ** 2 + j * l + j * r + l * r == i:
# #                     if j == l == r:
# #                         flag = True
# #                         count = 1
# #                         break
# #                     else:
# #                         flag = True
# #                         count = 3
# #                         break
# #             if flag:
# #                 break
# #         if flag:
# #             break            
# #     print(count)
# #     count = 0
# #     flag = False
ans = [0] * 10050
for j in range(1, n):
    for l in range(1, n):
        for r in range(1, n):
            value = j * j  + l * l + r * r + j * l + j * r + l * r
            if value < 10050:
                ans[value] += 1

for i in range(N):
    print(ans[i + 1])
# n = int(input())
# ans = [0 for _ in range(10050)]
# for i in range(1,105):
#     for j in range(1,105):
#         for k in range(1,105):
#             v = i*i+j*j+k*k+i*j+j*k+k*i;
#             if v<10050:
#                 ans[v]+=1   
# for i in range(n):
#     print(ans[i+1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
from collections import deque
n,x,y = map(int,input().split())
g = [[]for i in range(n)]
g[0].append(1)
g[n-1].append(n-2)
g[x-1].append(y-1)
g[y-1].append(x-1)
for i in range(1,n-1):
  g[i].append(i-1)
  g[i].append(i+1)
ans = [0]*(n-1)
def dfs(b,c):
  for i in g[b]:
    if a[i] > c+1:
      a[i] = c+1
      que.append([i,c+1])
    
for i in range(n):
  a = [999999999]*n
  a[i] = 0
  que = deque()
  que.append([i,0])
  while que:
    x,y = que.popleft()
    dfs(x,y)
  for j in a:
    if j == 0:
      continue
    ans[j-1] += 1
for i in ans:
  print(i//2)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
from collections import deque
n,x,y = map(int,input().split())
g = [[]for i in range(n)]
g[0].append(1)
g[n-1].append(n-2)
g[x-1].append(y-1)
g[y-1].append(x-1)
for i in range(1,n-1):
  g[i].append(i-1)
  g[i].append(i+1)
ans = [0]*(n-1)
def dfs(b,c):
  for i in g[b]:
    if a[i] > c+1:
      a[i] = c+1
      que.append([i,c+1])
    
for i in range(n):
  a = [999999999]*n
  a[i] = 0
  que = deque()
  que.append([i,0])
  while que:
    x,y = que.popleft()
    dfs(x,y)
  for j in a:
    if j == 0:
      continue
    ans[j-1] += 1
for i in ans:
  print(i//2)
### BUGGY CODE ###

n,x,y=map(int,input().split())
x-=1
y-=1
def dist(a,b):
	return min(abs(b-a),1+abs(a-x)+abs(b-y),1+abs(b-x)+abs(a-y))
#d==1
print(n)
for d in range(2,n):
	ans=0
	for i in range(n-d):
		lst=[]
		if i+d<n and dist(i,i+d)==d:
			lst.append(i+d)
		d0=d
		d0-=abs(x-i)
		d0-=1
		if d0>=0:
			if i<y-d0 and dist(i,y-d0)==d:
				lst.append(y-d0)
			if i<y+d0 and dist(i,y+d0)==d and y+d0<n:
				lst.append(y+d0)
		ans+=len(list(set(lst)))
	print(ans)

### FIXED CODE ###

n,x,y=map(int,input().split())
x-=1
y-=1
def dist(a,b):
	return min(abs(b-a),1+abs(a-x)+abs(b-y),1+abs(b-x)+abs(a-y))
#d==1
print(n)
for d in range(2,n):
	ans=0
	for i in range(n-d):
		lst=[]
		if i+d<n and dist(i,i+d)==d:
			lst.append(i+d)
		d0=d
		d0-=abs(x-i)
		d0-=1
		if d0>=0:
			if i<y-d0 and dist(i,y-d0)==d:
				lst.append(y-d0)
			if i<y+d0 and dist(i,y+d0)==d and y+d0<n:
				lst.append(y+d0)
		ans+=len(list(set(lst)))
	print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

N = int(readline())
A = [None] * N
for i in range(N):
  # 後ろからpopできるように逆順リストで持つ
  A[i] = list(map(lambda x:x - 1,map(int,readline().split())))[::-1]
  
# 今日試合ができる可能性がある人リスト
candi = set(range(N))

day = 0
while True:
  day += 1
  nex = set()
  done = set()
  for player in candi:
    if player in done:
      continue
    # player が試合できるかチェック
    if not A[player]:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if A[rival][-1] == player:
      # 試合できる
      A[player].pop()
      A[rival].pop()
      if A[player]:
        nex.add(player)
      done.add(player)
      if A[rival]:
        nex.add(rival)
      done.add(rival)
    else:
      # 試合できないが、明日も試合できる状態
      nex.add(player)
  if len(done) == 0:
    # 一試合もできなかった
    print(-1)
    exit(0)
  if len(nex) == 0:
    print(day)
    exit(0)
  candi = nex

### FIXED CODE ###

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

import sys
import numpy as np

rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n, k = rm()
a = (np.array(rl()) + 1)/2
ans = np.sum(a[:k])
for i in range(1, n-k+1):
    ans = max(ans, np.sum(a[i:i+k]))
print(ans)

### FIXED CODE ###

import sys
from itertools import accumulate

rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n, k = rm()
a = [(i+1)/2 for i in rl()]
a = [0] + list(accumulate(a))
ans = 0
for i in range(n-k+1):
    ans = max(ans, a[i+k] - a[i])
print(ans)
### BUGGY CODE ###

def main():
    import bisect
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort()
    for dc in range(M):
        A[-1] = A[-1]//2
        i = 1
        while i < N and A[-i-1] > A[-i]:
            A[-i-1],A[-i] = A[-i],A[-i-1]
            i += 1
    print(sum(A))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from heapq import heappush,heappop,heapify
from math import ceil
def main():
    N, M = (int(i) for i in input().split())
    A = [-int(i) for i in input().split()]
    heapify(A)
    for divcnt in range(M):
        tmp = ceil(heappop(A)/2)
        heappush(A,tmp)
    print(-sum(A))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

for i in range(N):
  print(str(A.index(i+1)+1), end=" ")






### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
List = [0]*N


for i, a in enumerate(A):
  List[int(a)-1] = str(i+1)

  
print(" ".join(List))
### BUGGY CODE ###

l,r = map(int, input().split())
ans = 2019

for i in range(l, r):
    for j in range(i+1, r+1):
        a = (i * j) % 2019
        if ans > a:
            ans = a
        if a == 0:
            break

print(ans)


### FIXED CODE ###

l,r = map(int, input().split())
ans = 2019

for i in range(l, min(l+2019, r)):
    for j in range(i+1, min(l+2019, r+1)):
        a = (i * j) % 2019
        ans = min(ans, a)

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

n = int(input())
s = input()
ans = 10**9
for i in range(n):
    count = 0
    key = s[i]
    count = (s[:i].count('W') + s[i+1:].count('E'))
    ans = min(ans,count)
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = 10**9
w = s.count('W')
e = s.count('E')
w_count = 0
e_count = 0
for i in range(n):
    if s[i] == 'W':
        w -= 1
        ans = min(ans,e+w_count)
        w_count += 1
    else:
        e -= 1
        ans = min(ans,e+w_count)
        e_count += 1

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

n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]


import math

M = 50 * n + 1

dp = [[float('inf')] * M for _ in range(n)]
s = min(s, M - 1)
dp[0][s] = 0

def inc(dp, i, j):
    c, d = cd[i][0], cd[i][1]
    for jj in range(M):
        dp[i][jj] = min(dp[i][jj], dp[i][j] + max(math.ceil((jj - j) / c), 0) * d)
    return dp

dp = inc(dp, 0, s)

while True:
    flag = False

    for i in range(m):
        u1, v1, a, b = uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3]
        for (u, v) in [(u1, v1), (v1, u1)]:
            for j in range(M):
                if j + a < M:
                    tmp = dp[u][j + a] + b
                    if tmp < dp[v][j]:
                        dp[v][j] = tmp
                        flag = True

                    c, d = cd[v][0], cd[v][1]
                    for jj in range(M):
                        tmp = dp[v][j] + max(0, math.ceil((jj - j) / c)) * d
                        if tmp < dp[v][jj]:
                            dp[v][jj] = tmp
                            flag = True


    if flag == False:
        break

for t in range(1, n):
    print(min(dp[t]))


### FIXED CODE ###

n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]


import math

M = 50 * n + 1
s = min(s, M - 1)

dp = [[float('inf')] * M for _ in range(n)]

dp[0][s] = 0
c, d = cd[0][0], cd[0][1]
for jj in range(M):
    dp[0][jj] = min(dp[0][jj], dp[0][s] + max(math.ceil((jj - s) / c), 0) * d)

while True:
    flag = False

    for i in range(m):
        u1, v1, a, b = uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3]
        for u, v in [(u1, v1), (v1, u1)]:
            for j in range(M - a):
                tmp = dp[u][j + a] + b
                if tmp < dp[v][j]:
                    dp[v][j] = tmp
                    flag = True

            c, d = cd[v][0], cd[v][1]
            for jj in range(c, M):
                tmp = dp[v][jj - c] + d
                if tmp < dp[v][jj]:
                    dp[v][jj] = tmp
                    flag = True

    if flag == False:
        break

for t in range(1, n):
    print(min(dp[t]))
### BUGGY CODE ###

n = int(input())

divisors = []
for i in range(1, n+1):
	if n % i == 0:
		divisors.append(i)

m = len(divisors)

a = divisors[m//2-1]
b = divisors[m//2]

print(a+b-2)


 



### FIXED CODE ###

n = int(input())

divisors = []
for i in range(1, int(n**0.5)+1):
	if n % i == 0:
		divisors.append(i)

#m = len(divisors)

#a = divisors[m//2-1]
#b = divisors[m//2]

a= max(divisors)
b=n//a
#print(a)
#print(b)
print(a+b-2)