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

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  m = max(m,len(g[_]))
  mi = _
print(m)
g2 = [[0]*(m+1) for i in range(n)]
deq = deque([mi])
vi = [0] * n
vi[mi] = 1
d = dict()
while deq:
  cur = deq.popleft()
  for i in g[cur]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      deq.append(i)
      for k in range(1,m+1):
        if g2[cur][k] == 1 or g2[i][k] == 1:
          continue
        else:
          g2[cur][k] = 1
          g2[i][k] = 1
          d[(min(cur,i),max(cur,i))] = k
          break
for i in l:
  print(d[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  if len(g[_]) > m:
    m = len(g[_])
    mi = _
print(m)
g2 = [[] for i in range(n)]
stack = [(mi,-1)]
vi = [0] * n
vi[mi] = 1
d = dict()
while stack:
  pre,prei = stack.pop()
  c = 0
  for i in g[pre]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      c += 1
      if c == prei:
        c += 1
      d[(min(pre,i),max(pre,i))] = c
      stack.append((i,c))
for i in l:
  print(d[i])
### BUGGY CODE ###

import numpy as np
H, W, D = map(int, input().split())

grid = [[] for h in range(H)]
for h in range(H):
    grid[h] = [int(_) for _ in input().split()]

np_grid = np.array(grid).ravel()


Q = int(input())
for q in range(Q):
    ans = 0
    L, R = map(int, input().split())
    if L == R:
        print(ans)
        continue
    else:
        while L != R:
            h_before = np.where(np_grid==L)[0][0] // 3
            w_before = np.where(np_grid==L)[0][0] % 3
            h_after = np.where(np_grid==(L+D))[0][0] // 3
            w_after = np.where(np_grid==(L+D))[0][0] % 3
            L += D
            ans += (abs(h_before - h_after) + abs(w_before - w_after))
        print(ans)

### FIXED CODE ###

import numpy as np
H, W, D = map(int, input().split())
grid = [[] for h in range(H)]

for h in range(H):
    grid[h] = [int(_) for _ in input().split()]
memo = [None] * (H * W + 1)
for h in range(H):
    for w in range(W):
        memo[grid[h][w]] = (h, w)

distance = [0 for i in range(H * W + 1)]

for d in range(D + 1, H * W + 1):
    h_1, w_1 = memo[d]
    h_0, w_0 = memo[d - D]
    distance[d] = distance[d - D] + abs(h_1 - h_0) + abs(w_1 - w_0)

Q = int(input())
for q in range(Q):
    L, R = map(int, input().split())
    print(distance[R] - distance[L])
### BUGGY CODE ###

N = int(input())
list = [int(i) for i in input().split()]

count = 0

for j in range(N):
    #print("j="+str(j))
    jj = list[j]
    for k in range(j+1):
        #print("k="+str(k))
        if(list[k] < jj):
            break

        if(k == j):
            count += 1
            break


print(count)


### FIXED CODE ###

N = int(input())
list = [int(i) for i in input().split()]

ans = 0
min = list[0]

for j in range(N):
    if (min  >= list[j]):
        ans += 1
        min = list[j]
    else:
        continue

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

X = input()
while 'ST' in X:
    X = X.replace('ST','',1)
print(len(X))

### FIXED CODE ###

X = input()
st = []
for s in X:
    if s == 'S': st.append(s)
    if s == 'T':
        if (not st) or st[-1] == 'T': st.append(s)
        if st[-1] == 'S': st.pop()
print(len(st))
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())
g = [[] for i in range(n)]
h = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
  h[y].append(x)
hukasa = [0]*n
MIN = float("inf")
for i in range(n):
  MIN = min(MIN,len(h[i]))
def dfs(x,y):
  for k in g[x]:
    if hukasa[k] < y+1:
      que.append([k,y+1])
for i in range(n):
  if MIN == len(h[i]):
    que = deque([])
    que.append([i,0])
    while que:
      x,y = que.popleft()
      hukasa[x] = y
      dfs(x,y)
for i in range(n):
  hukasa[i] = [hukasa[i],i]
hukasa.sort()
dp = [0] * n
for l,i in hukasa:
  for j in g[i]:
    if dp[j] < dp[i]+1:
      dp[j] = dp[i]+1
print(max(dp))

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
g = [[] for i in range(n)]
h = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
  h[y].append(x)
topo = []
hukasa = [0] * n
hairu = [0]*n
que = deque([])
for i in range(n):
  hairu[i] = len(h[i])
  if hairu[i] == 0:
    topo.append(i)
    que.append(i)
def dfs(x):
  for i in g[x]:
    hairu[i]-=1
    if hairu[i] == 0:
      topo.append(i)
      que.append(i)
while que:
  x = que.popleft()
  dfs(x)
def dfs2(x):
  for i in g[x]:
    hukasa[i] = max(hukasa[i],hukasa[x]+1)
for i in topo:
  dfs2(i)
print(max(hukasa))
### BUGGY CODE ###

def main(R,C,K,V):
    dp = [[[0,0,0,0] for _ in range(C)] for _ in range(R)]
    dp[0][0][1] = V[0][0]
    for i in range(R):
        for j in range(C):
            for n in range(4):
                if n!=0:
                    if i != 0 and n==1:
                        dp[i][j][n] = max(dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])+V[i][j]
                    if j != 0:
                        dp[i][j][n] = max(dp[i][j][n],dp[i][j-1][n],dp[i][j-1][n-1]+V[i][j])
                if n==0:
                    if i != 0:
                        dp[i][j][n] = max(dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])

    print(max(dp[-1][-1]))

if __name__ == '__main__':
    R,C,K = map(int,input().split())
    rcv = [list(map(int,input().split())) for _ in range(K)]
    V = [[0]*C for _ in range(R)]
    for i in range(K):
        r,c,v = rcv[i]
        r -= 1
        c -= 1
        V[r][c] = v
    main(R,C,K,V)

### FIXED CODE ###

def main(R,C,K,V):
    dp = [0]*(4*R*C)
    dp[1+4*0+4*C*0] = V[0][0]
    for k in range(4*R*C):
        n = k%4
        j = k//4%C
        i = k//(4*C)
        if n!=0:
            if i != 0 and n==1:
                dp[k] = max(dp[k-4*C-n:k-4*C-n+4])+V[i][j]
            if j != 0:
                dp[k] = max(dp[k],dp[k-4],dp[k-5]+V[i][j])
        if n==0:
            if i != 0:
                dp[k] = max(dp[k-4*C-n:k-4*C-n+4])

    print(max(dp[-5:-1]))

if __name__ == '__main__':
    R,C,K = map(int,input().split())
    C += 1
    rcv = [list(map(int,input().split())) for _ in range(K)]
    V = [[0]*C for _ in range(R)]
    for i in range(K):
        r,c,v = rcv[i]
        r -= 1
        c -= 1
        V[r][c] = v
    main(R,C,K,V)
### BUGGY CODE ###

import itertools
import collections

# 解説を読んだ。
n, x, y = [int(x) for x in input().split()]

nodes = [i for i in range(1, n + 1)]
patterns = itertools.combinations(nodes, 2)

distannces = []
distannces_append = distannces.append
for p in patterns:
    routes = (
        abs(p[1] - p[0]),
        abs(x - p[0]) + 1 + abs(p[1] - y),
        abs(y - p[0]) + 1 + abs(p[1] - x)
    )
    distannces_append(min(routes))

c = collections.Counter(distannces)

# distannces_count = distannces.count
s = '\n'.join((str(c[k]) for k in range(1, n)))
print(s)

# 後半 TLE したのでリストの関数をオブジェクトに格納した: だめ
# collections.Counter 導入: だめ。


### FIXED CODE ###

from collections import deque

n, x, y = [int(x) for x in input().split()]
x -= 1
y -= 1
BIG = 65521
ans = {i: 0 for i in range(n)}


def bfs(start_v):
    """ある始点からほかの全点に行くまでの最短距離を求める。"""
    qu = deque()
    qu_append = qu.append
    qu_popleft = qu.popleft
    qu_append(start_v)
    # 始点からvに移動するまでの最短距離: dist[v]
    dist = [BIG] * n

    def push(v, d):
        """始点からvまでの最短距離が算出されていないときに，その距離を保存し，
        キューに頂点vを追加する。"""
        if dist[v] != BIG:
            # 既に訪問済みで距離が求められている。
            return
        dist[v] = d
        qu_append(v)

    push(start_v, 0)

    while len(qu):
        v = qu_popleft()
        # 始点からvの次の頂点へ移動する距離。
        d = dist[v] + 1
        if v < n - 1:
            push(v + 1, d)
        if v > 0:
            push(v - 1, d)
        if v == x:
            push(y, d)
        if v == y:
            push(x, d)

    for i in range(n):
        if dist[i] != 0:
            ans[dist[i]] += 1


def main():
    for i in range(n):
        bfs(i)

    for i in range(1, n):
        print(ans[i] // 2)


if __name__ == '__main__':
    main()

# TLE
### BUGGY CODE ###

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    K = ii()

    substring = set()
    for i in range(1, len(S)+1):
        for j in range(i):
            if j == i:
                break
            substring.add(S[j:i])
    ret = sorted(list(substring))
    print(ret[K-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    K = ii()

    substring = set()
    for i in range(len(S)):
        for j in range(i+1, i+K+1):
            substring.add(S[i:j])
    ret = sorted(list(substring))
    print(ret[K-1])


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

import sys
sys.setrecursionlimit(200000)

n, q = map(int, input().split())
edges = [[] for _ in range(n)]
counter = [0] * n
for a, b in [list(map(int, input().split())) for _ in range(n - 1)]:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for p, x in [list(map(int, input().split())) for _ in range(q)]:
    counter[p - 1] += x

def dfs(p, i, v):
    counter[i] += v
    for j in edges[i]:
        if j != p:
            dfs(i, j, counter[i])

dfs(-1, 0, 0)

print(' '.join(str(c) for c in counter))

### FIXED CODE ###

n, q = map(int, input().split())
edges = [[] for _ in range(n)]
counter = [0] * n
for a, b in [list(map(int, input().split())) for _ in range(n - 1)]:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for p, x in [list(map(int, input().split())) for _ in range(q)]:
    counter[p - 1] += x

ret = [-1] * n
ret[0] = counter[0]
q = [0]
index = 0
while index < len(q):
    i = q[index]
    index += 1
    for j in edges[i]:
        if ret[j] < 0:
            q.append(j)
            ret[j] = counter[j] + ret[i]

print(' '.join(str(c) for c in ret))
### BUGGY CODE ###

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = []
for i in range(n+1):
    b_list.append(a_list.count(i))
b_list.sort(reverse = True)
f = sum(b_list[:k:])
print(n-f)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
b = collections.Counter(a_list)
d = b.most_common()[k:]
sum = 0
for i in d:
    sum += i[1]
print(sum)
### BUGGY CODE ###

import sys

input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    h, w = MI()
    s = [[c == "#" for c in input()[:-1]] for _ in range(h)]
    if w == 2:
        s = [list(sc) for sc in zip(*s)]
        h, w = w, h
    # p2D(s)
    t = [[-1] * (w - 1) for _ in range(h - 1)]
    for i in range(h - 1):
        si = s[i]
        si1 = s[i + 1]
        t[i] = [1 - (sum(si[j:j + 2]) + sum(si1[j:j + 2])) % 2 for j in range(w - 1)]
    # p2D(t)
    # print()
    ti=t[0]
    for i in range(1, h - 1):
        ti1=ti
        ti=t[i]
        for j in range(w - 1):
            if ti[j]: ti[j] = ti1[j] + 1
    # p2D(t)
    ans = 0
    for i in range(h - 1):
        jtol = [0] * (w - 1)
        jtor = [0] * (w - 1)
        ti=t[i]
        # 高さ、位置の順
        stack = [[-1, 0]]
        for j in range(w - 1):
            h=ti[j]
            while stack[-1][0] >= h: stack.pop()
            jtol[j] = stack[-1][1]
            stack.append([h, j + 1])

        stack = [[-1, w - 1]]
        for j in range(w - 2, -1, -1):
            h=ti[j]
            while stack[-1][0] >= h: stack.pop()
            jtor[j] = stack[-1][1]
            stack.append([h, j])

        for j in range(w - 1):
            tmp = (jtor[j] - jtol[j] + 1) * (ti[j] + 1)
            if tmp > ans: ans = tmp
    print(ans)

main()


### FIXED CODE ###

import sys

input=sys.stdin.readline
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())

def main():
    h, w = MI()
    s = [[c == "#" for c in input()[:-1]] for _ in range(h)]
    #if w == 2:
    #    s = [list(sc) for sc in zip(*s)]
    #    h, w = w, h
    # p2D(s)
    t = [[-1] * (w - 1) for _ in range(h - 1)]
    for i in range(h - 1):
        si = s[i]
        si1 = s[i + 1]
        t[i] = [1 - (sum(si[j:j + 2]) + sum(si1[j:j + 2])) % 2 for j in range(w - 1)]
    # p2D(t)
    # print()
    ti=t[0]
    for i in range(1, h - 1):
        ti1=ti
        ti=t[i]
        for j in range(w - 1):
            if ti[j]: ti[j] = ti1[j] + 1
    # p2D(t)
    ans = 0
    for i in range(h - 1):
        jtol = [0] * (w - 1)
        jtor = [0] * (w - 1)
        ti=t[i]
        # 高さ、位置の順
        stack = [[-1, 0]]
        for j in range(w - 1):
            tij=ti[j]
            while stack[-1][0] >= tij: stack.pop()
            jtol[j] = stack[-1][1]
            stack.append([tij, j + 1])

        stack = [[-1, w - 1]]
        for j in range(w - 2, -1, -1):
            tij=ti[j]
            while stack[-1][0] >= tij: stack.pop()
            jtor[j] = stack[-1][1]
            stack.append([tij, j])

        for j in range(w - 1):
            tmp = (jtor[j] - jtol[j] + 1) * (ti[j] + 1)
            if tmp > ans: ans = tmp
    print(max(ans,h,w))

main()
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
CA = Counter(A)
all_count = 0
for ca in CA.values():
  all_count += ca*(ca-1)//2

for a in A:
  print(all_count - (A.count(a)-1))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
B = Counter(A)
ans = 0

for i in B.values():
  ans += i*(i-1)//2
for a in A:
  k = B[a]
  print(ans - (k*(k-1)//2)+((k-1)*(k-2)//2))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
for i in range(1, n):
    min_tmp = float('inf')
    for j in range(1, k+1):
        if j > i:
            break
        min_tmp = min(min_tmp, dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min_tmp
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
for i in range(1, n):
    min_tmp = float('inf')
    for j in range(1, k+1):
        if j > i:
            break
        min_tmp = min(min_tmp, dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min_tmp
print(dp[-1])
### BUGGY CODE ###

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

def cat_snuke():	
	for i in l:
		for j in bone:
			if i == j:
				print("POSSIBLE")
				return 0
		
	print("IMPOSSIBLE")

cat_snuke()


### FIXED CODE ###

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

ans=list(set(l) & set(bone))
if len(ans)!=0:
	print("POSSIBLE")
else:			
	print("IMPOSSIBLE")
### BUGGY CODE ###

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

a.sort()
cur = a[0]
ans1 = 1
ans = 1

for i in range(n - 1):
    if a[i + 1] - a[i] <= 2:
        cur = a[i]
        ans1 = a.count(cur) + a.count(cur + 1) + a.count(cur + 2)

        if ans < ans1:
            ans = ans1
        ans1 = 0

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
max_a = max(a)

b = [0]*(max_a + 2)

for i in a:
    b[i] += 1

ans = 0
for i in range(max_a + 1):
    tmp = b[i-1] + b[i] + b[i+1]
    ans = max(ans, tmp)

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

a, b, c, d, e, f = [int(x) for x in input().split()]
threshold = e / (100 + e) * 100
max_concent = 0
max_total = 0
max_suger = 0
max_try = int(f / 10 * a)
for i in range(max_try):
    for j in range(max_try):
        for k in range(max_try):
            for l in range(max_try):                
                water = a * i * 100 + b * j * 100
                suger = c * k + d * l   
                if water == 0:
                    break
                concentration = suger / (water + suger) * 100
                if (water + suger > f or concentration > threshold) :
                    break
                else:
                    if concentration > max_concent:
                        max_concent = concentration
                        max_total = water + suger
                        max_suger = suger
print("{} {}".format(max_total, max_suger))

### FIXED CODE ###

import math
a, b, c, d, e, f = [int(x) for x in input().split()]
threshold = e / (100 + e) * 100
max_concent = 0
max_total = 0
max_suger = 0
max_suger_try = int(threshold/100*f//c)
for i in range(31):
    for j in range(31):
        for k in range(max_suger_try):
            for l in range(max_suger_try):
                water = a * i * 100 + b * j * 100
                suger = c * k + d * l   
                if water == 0:
                    break
                concentration = suger / (water + suger) * 100
                if (water + suger > f or concentration > threshold) :
                    break
                else:
                    if concentration > max_concent:
                        max_concent = concentration
                        max_total = water + suger
                        max_suger = suger
if max_total == 0:
    max_total = a * 100
print("{} {}".format(max_total, max_suger))
### BUGGY CODE ###

def reverse(s):
  ret = ''
  len_ = len(s) - 1
  for i in range(len(s)):
    ret += s[len_ - i]
  return ret

S = input()
N = int(input())
for i in range(N):
  str_ = input()
  if ' ' in str_:
    c = str_.split()
    if c[1] == '2':
      S = S + c[2]
    else:
      S = c[2] + S
  else:
    S = reverse(S)
print(S)

### FIXED CODE ###

import queue
def reverse(s):
  ret = ''
  len_ = len(s) - 1
  for i in range(len(s)):
    ret += s[len_ - i]
  return ret

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


p_a = queue.LifoQueue()
rp_a = queue.Queue()
p_b = queue.Queue()
rp_b = queue.LifoQueue()
flag = False
for i in range(N):
  s = input()
  if s[0] == '1':
    flag = not flag   
  else:
    if (s[2] == '2' and not flag) or (s[2] == '1' and flag) :
      p_b.put(s[4])
    elif (s[2] == '2' and flag) or (s[2] == '1' and not flag) :
  	  p_a.put(s[4])
s_a = ''
s_b = ''
while not p_a.empty():
  s_a += p_a.get()
while not p_b.empty():
  s_b += p_b.get()
ret = s_a + S + s_b
if flag:
  ret = reverse(ret)

print(ret)
### BUGGY CODE ###

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

def cnt_uniq(li):
    uniq = list(set(li))
    ret = []
    for i in uniq:
        ret.append(li.count(i))
    return ret

uniq = sorted(cnt_uniq(a), reverse = True)[k:]
print(sum(uniq))

### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))

def cnt_uniq(li):
    return Counter(li).values()

uniq = sorted(cnt_uniq(a), reverse = True)[k:]
print(sum(uniq))
### BUGGY CODE ###

N = int(input())
S = input()
A = [1 if(S[i]=='E') else 0 for i in range(N)]
ans = min(sum(A[1:]), N-sum(A[:]))
for i in range(1,N):
  ans = min(ans, i - sum(A[:i])+ sum(A[i+1:]))
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
A = [1 if S[0]=='E' else 0]
for i in range(1,N):
  A.append(1 if S[i]=='E' else 0)
  A[i] += A[i-1]
ans = min(N-1-A[N-2], A[N-1]-A[0])
for i in range(1,N):
  ans = min(ans, i-A[i-1]+A[N-1]-A[i])
print(ans)
### BUGGY CODE ###

n = int(input())
c = list(input())
cFixed = [x for x in c]
cFixed.sort()
ans = 0
for i in range(n):
	if c[i] != cFixed[i]:
		for j in range(i+1 , n):
			if c[j] == "R" and c[j] != cFixed[j]:
				c[i] = "R"
				c[j] = "W"
				ans += 1


print(ans)


### FIXED CODE ###

n = int(input())
c = list(input())
cFixed = [x for x in c]
cFixed.sort()
lastR = -1
for i in range(n):
	if cFixed[i] == "R":
		lastR = i
ans = 0
for i in range(lastR+1):
	if c[i] == "W":
		ans += 1

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

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid
    if cnt >= 20:
        print(s[1000])
print(high,1111)
sys.stdout.flush()
s = input()
exit()

### FIXED CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid

print(high)
sys.stdout.flush()
s = input()
if s[0] == "V":
    exit()
else:
    print(low)
    sys.stdout.flush()
    s = input()
    exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
for i in range(m):
    a[0]//=2
    a.sort(reverse=True)
print(sum(a))


### FIXED CODE ###

import sys
import heapq
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=-a[i]
heapq.heapify(a)
for i in range(m):
  heapq.heappushpop(a,-(-a[0]//2))
print(-sum(a))