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

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, p: "List[int]", S: "List[str]"):
    ac_list = []
    for (pi, si) in zip(p, S):
        if si=="AC":
            ac_list.append(pi)
    ac_list = sorted(list(set(ac_list)))
    num_ans = len(ac_list)

    num_penalty = 0
    for i, (pi, si) in enumerate(zip(p, S)):
        # check ac
        if pi in ac_list:
            if si == "WA":
                num_penalty += 1
            else:
                tmp = ac_list.remove(pi)

    print(num_ans, num_penalty)
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    p = [int()] * (M)  # type: "List[int]"
    S = [str()] * (M)  # type: "List[str]"
    for i in range(M):
        p[i] = int(next(tokens))
        S[i] = next(tokens)
    solve(N, M, p, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, p: "List[int]", S: "List[str]"):
    wa_flag = [0] * N
    num_penalty = 0
    for i in range(M):
        if S[i] == "WA":
            if wa_flag[p[i]-1] != -1:
                wa_flag[p[i]-1] += 1
        else:
            if wa_flag[p[i]-1] != -1:
                num_penalty += wa_flag[p[i]-1]
                wa_flag[p[i]-1] = -1
    num_ac = wa_flag.count(-1)
    print(num_ac, num_penalty)
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M = map(int, input().split())
    p = [None] * M
    S = [None] * M
    for i in range(M):
        pi, si = input().split()
        p[i] = int(pi)
        S[i] = str(si)
    solve(N, M, p, S)

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

s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=ab+a
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=ab*3+a
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)


### FIXED CODE ###

s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=(ab+a)%m
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=(ab*3+a)%m
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)
### BUGGY CODE ###

N = int(input()) #N: ボールの個数

A = list(map(int, input().split()))
count_A = [0]*(N+1)
count_pattern = [0]*(N+1)

for i in A:
    if count_A[i]==0:
        a = A.count(i)
        count_A[i] = a
        count_pattern[i] = (a*(a-1)//2)

max = sum(count_pattern)

for i in range(N):
    a = A[i]
    b = count_A[a]
    print(max - (b-1))


### FIXED CODE ###

N = int(input()) #N: ボールの個数

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

from collections import defaultdict

d = defaultdict(int)
for i in A:
    d[i] += 1
max = sum([d[i]*(d[i]-1)//2 for i in range(1,N+1)])
ans = [max - d[i] + 1 for i in A]

for x in ans:
    print(x)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
# print(n)
# print(A)

B = [0]*n
for i in range(n):
    B[i] = A[i] - (i+1)

B.sort()
# print(B)
bmin = min(B)
bmax = max(B)
ans = 10**18
for b in range(bmin,bmax+1):
    ret = 0
    for bi in B:
        ret += abs(bi-b)
    ans = min(ans, ret)
print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = []
for i in range(n): B.append(A[i] - (i+1))
B.sort()
r = B[n//2] # median right
l = B[n//2] if n%2 else B[n//2-1] # median left
# print(n,A)
# print(B)
# print(l,r)
ans_l = 0
ans_r = 0
for bi in B:
    ans_l += abs(bi-l)
    ans_r += abs(bi-r)
print(min([ans_l, ans_r]))
### BUGGY CODE ###

import math
K=int(input())
c = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      if i == j == k:
        c += i
      elif i == j:
        c += math.gcd(i,k)
      elif i == k:
        c += math.gcd(i,j)
      elif j == k:
        c += math.gcd(i,k)
      else:
        c += math.gcd(math.gcd(i, j), k)
print(c)

### FIXED CODE ###

import math
K=int(input())
c = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    if math.gcd(i,j) == 1:
      c += K
    else:
      for k in range(1,K+1):
        if i == j == k:
          c += i
        elif i == j:
          c += math.gcd(i,k)
        elif i == k:
          c += math.gcd(i,j)
        elif j == k:
          c += math.gcd(i,k)
        else:
          c += math.gcd(math.gcd(i, j), k)
print(c)
### BUGGY CODE ###

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

mini = float('inf')

if sum(A[0:(N//2)]) < sum(A[(N//2):N]):
    for i in range(N//2 + 1):
        if abs(sum(A[0:i+(N//2)]) - sum(A[i+(N//2):N])) < mini:
            mini = abs(sum(A[0:i+(N//2)]) - sum(A[i+(N//2):N]))
elif sum(A[0:(N//2)]) > sum(A[(N//2):N]):
    for i in range(N//2 + 1):
        if abs(sum(A[0:(N//2)-i]) - sum(A[(N//2)-i:N])) < mini:
            mini = abs(sum(A[0:(N//2)-i]) - sum(A[(N//2)-i:N]))
else:
    print(0)
    exit()

'''
for i in range(N):
    if abs(sum(A[0:i]) - sum(A[i:N])) < mini:
        mini = abs(sum(A[0:i]) - sum(A[i:N]))
    if abs(sum(A[0:-i]) - sum(A[-i:N])) < mini:
        mini = abs(sum(A[0:-i]) - sum(A[-i:N]))
    if mini == 0:
        break
'''

print(mini)


### FIXED CODE ###

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

mini = float('inf')

cumsum = list(itertools.accumulate(A))
A.reverse()
rev = list(itertools.accumulate(A))
rev.reverse()
cumsum.pop()
rev.pop(0)

for i, j in zip(cumsum,rev):
    if abs(i-j) < mini:
        mini = abs(i-j)

print(mini)
### BUGGY CODE ###

import numpy

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

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  for i in range(1,m):
    if A_sum[i-1]>=sum_left/2:
      break
  sum1=A_sum[i-1]
  if i!=1:
    if A_sum[i-1]+A_sum[i-2]>sum_left:
      sum1=A_sum[i-2]
  sum2=sum_left-sum1

  sum_right=A_sum[N-1]-sum_left
  for i in range(m+1,N):
    if A_sum[i-1]-sum_left>=sum_right/2:
      break
  sum3=A_sum[i-1]-sum_left
  if i!=m+1:
    if A_sum[i-1]+A_sum[i-2]-2*sum_left>sum_right:
      sum3=A_sum[i-2]-sum_left
  sum4=sum_right-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
from itertools import accumulate

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

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  i=bisect_left(A_sum,sum_left/2)
  sum1=A_sum[i]
  if i!=0:
    if A_sum[i]+A_sum[i-1]>sum_left:
      sum1=A_sum[i-1]
  sum2=sum_left-sum1

  sum_right=A_sum[N-1]-sum_left
  i=bisect_left(A_sum,sum_left+sum_right/2)
  sum3=A_sum[i]-sum_left
  if i!=m:
    if A_sum[i]+A_sum[i-1]-2*sum_left>sum_right:
      sum3=A_sum[i-1]-sum_left
  sum4=sum_right-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

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

MOD = 10**9+7


def main():
  S = input()
  L = len(S)
  dp = [[0] *13 for _ in range(L+1)]
  dp[0][0] = 1
  mul = 1
  
  for i in range(L):
    x = S[-(i+1)]
    if x == '?':
      for k in range(10):
        for j in range(13):
          dp[i+1][(mul * k + j)%13] += dp[i][j]
          dp[i+1][(mul * k + j)%13] %= MOD
    else:
      k = int(x)
      for j in range(13):
        dp[i+1][(mul * k + j)%13] += dp[i][j]
        dp[i+1][(mul * k + j)%13] %= MOD
    mul = mul * 10 %13
  print(dp[L][5])
    
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
 
s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ [ (b*i+j)%13 for i in range(1,10) ] for j in range(13) ] )
#
dp= [ 0 ] * 13
dp[0] = 1
j= 0
for c in reversed(s):
    tmp = dp.copy()
    #
    if c=="0": pass
    elif c=="?":
        bset = mmap[j]
        for m,num in enumerate(tmp):
            if num==0: continue
            for idx in bset[m]: dp[idx]+=num
        #
        for i in range(13): dp[i]%=MOD
    else:
        b= mmap[j][0][int(c)-1]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
    #
    if j==5: j=0
    else: j+=1
#
print(dp[5])
### BUGGY CODE ###

#!/usr/bin/python3

import sys
import resource
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def getmlen(cur, p, n, a, mlen, dp, nbs, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, n, a, mlen, dp, nbs, ntail)

    dp[idx] = ov
    return


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

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 for i in range(n) ]
dp = [ float('inf') for i in range(n) ]

getmlen(0, -1, n, a, mlen, dp, nbs, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])
### BUGGY CODE ###

s = list(input())
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    flag = 1 if s[i]=='?' else 0 #?だったら1
    if flag==1:
        for a in range(10):#i+1桁目の数字(0-9)
            for j in range(13): #あまり(0-12)
                dp[i+1][(j*10+a)%13] += dp[i][j] #i桁目の余りの10倍とi桁目を足して余りをだす
    else:
        for j in range(13):
            a = int(s[i])
            dp[i+1][(j*10+a)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j]%=10**9+7
print(dp[n][5])

### FIXED CODE ###

s = list(input())
n = len(s)

mod = 10**9+7
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    flag = 1 if s[i]=='?' else 0 #?だったら1
    if flag==1:
        for a in range(10):#i+1桁目の数字(0-9)
            for j in range(13): #あまり(0-12)
                dp[i+1][(j*10+a)%13] += dp[i][j] #i桁目の余りの10倍とi桁目を足して余りをだす
    else:
        for j in range(13):
            a = int(s[i])
            dp[i+1][(j*10+a)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j]%=10**9+7
        
print(dp[n][5])
### BUGGY CODE ###

import math
K=int(input())
result=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            result+=math.gcd(math.gcd(a,b),c)
print(result)

### FIXED CODE ###

from math import gcd
K=int(input())
result=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            result+=gcd(gcd(a,b),c)
print(result)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from bisect import bisect,insort
n = int(readline())
ppp = list(map(int,readline().split()))

q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
le = [-1,-1,n,n]
ans = 0
for i, p in q:
    l_i = bisect(le,i)
    LL = le[l_i-2]
    LR = le[l_i-1]
    RL = le[l_i]
    RR = le[l_i+1]
    ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
    insort(le,i)

print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter

n = int(readline())
ppp = list(map(int,readline().split()))

def BIT_add(i,x):
    while i <= n:
        tree[i] += x
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
      i = 0
      s = 0
      step = 1<<(n.bit_length()-1)
      while step:
          if i+step <= n and s + tree[i+step] < x:
              i += step
              s += tree[i]
          step >>= 1
      return i+1

q = sorted(enumerate(ppp,1),key=itemgetter(1),reverse=True)
tree = [0]*(n+1)

ans = 0
for i, p in q:
    L = BIT_sum(i) # 左にある既に書き込んだ数の個数
    BIT_add(i,1)
    R = n-p-L # 右にある既に書き込んだ数の個数
    LL = BIT_search(L-1) if L >= 2 else 0
    LR = BIT_search(L) if L >= 1 else 0
    RL = BIT_search(L+2) if R >= 1 else n+1
    RR = BIT_search(L+3) if R >= 2 else n+1
    ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
print(ans)
### BUGGY CODE ###

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

keiro = [1]

flag = True
now = 1
start = 0
loopN = 0
loop_list = []
while flag:
    if A[now-1] in keiro:
        flag = False
        start = keiro.index(A[now-1])
        loopN = len(keiro[start:])
        loop_list = keiro[start:]
    else:
        keiro.append(A[now-1])
        now = A[now-1]

if K - start >= 0:
    print(loop_list[(K - start) % loopN])
else:
    print(keiro[K])


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
keiro = [1]
keiro_set = {1}
flag = True
now = 1
start = 0
loopN = 0
loop_list = []
not_loop = False
for i in range(N):
    now = A[now - 1]
    if now in keiro_set:
        start = keiro.index(now)
        loop_list = keiro[start:]
        loopN = len(loop_list)
        break
    else:
        keiro.append(now)
        keiro_set.add(now)
    if i + 2 > K:
        not_loop = True
        break
if not_loop:
    print(keiro[K])
elif K - start >= 0:
    print(loop_list[(K - start) % loopN])
else:
    print(keiro[K])
### BUGGY CODE ###

s=input()



"""
例)
1817181712114の
18171が2019で割り切れるかどうかを判断する。

18171は(181712114-2114)/10000となるので、
181712114mod2019＝2114mod2019の時、2019で割り切れる。

1817181712114mod2019
 817181712114mod2019
  17181712114mod2019
   7181712114mod2019
    181712114mod2019
     81712114mod2019
      1712114mod2019
       712114mod2019
    　　・・・・
とmodを調べていき、値が同じペアは割り切れる。
"""

result=0

#初期値が0の辞書
from collections import defaultdict
mod_num = defaultdict(lambda: 0) 

for i in range(1,len(s)+1):
    temp = int(s[len(s)-i:])
    if temp%2019==0:
        result+=1
    else:
        result+=mod_num[temp%2019]
        mod_num[temp%2019]+=1


print(result)





### FIXED CODE ###

s=input()



"""
◆エッセンス1：割り切れるとは、二つに分けた数字のmodが一緒
例)
1817181712114の
18171が2019で割り切れるかどうかを判断する。

18171は(181712114-2114)/10000となるので、
181712114mod2019＝2114mod2019の時、2019で割り切れる。

1817181712114mod2019
 817181712114mod2019
  17181712114mod2019
   7181712114mod2019
    181712114mod2019
     81712114mod2019
      1712114mod2019
       712114mod2019
    　　・・・・
とmodを調べていき、値が同じペアは割り切れる。
"""

"""
◆エッセンス2：大きい数字は都度modを取る

これだけでもループは1回になるんだけど、
|S|が長すぎてTLEとなってしまう（|S|は10**5）
1234567 mod 2019
=(1*10**7)mod2019 + (234567mod2019)
=(1*10mod2019 * 10**6mod2019)+ (234567mod2019)

10**nを毎回modを取ることで、計算する数字の長さを短くする。

"""



#modの値を保持する配列
cnt=[0]*2019
#mod2019 =0 は、それ一つで割り切れるので。引き算をする必要が無い。
cnt[0]=1

#10の倍数を保持する
fac=1
ss=0
for i in range(len(s)):
    #後ろの数字から順番にとってくる
    ss += int(s[len(s)-i-1])*fac
    ss%=2019
    fac=fac*10
    fac%=2019
    cnt[ss]+=1
    

result=0
for c in cnt:
    result+=c*(c-1)//2

print(result)
### BUGGY CODE ###

N = int(input())
s_list = []
for i in range(N):
  s_list.append(''.join(sorted(input())))
c = 0
for i in range(N):
  for j in range(i+1,N):
    if (s_list[i] == s_list[j]):
      c += 1
print(c)

### FIXED CODE ###

import collections
N = int(input())
s_list = []
for i in range(N):
  s_list.append(''.join(sorted(input())))
s_list = collections.Counter(s_list)
def f(n):
  return int(n*(n+1)/2)
result = sum([f(n-1) for n in s_list.values()])
print(result)
### BUGGY CODE ###

n=int(input())
li=list(map(int,input().split()))
li.sort()
ans=li[0]
for i in range(1,n):
    ans*=li[i]
    if ans>1000000000000000000:
        exit
    else:
        pass
    
if ans>1000000000000000000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys
n=int(input())
li=list(map(int,input().split()))
li.sort()
if li[0]==0:
  print(0)
  sys.exit()
else:
  ans=1
  for i in li:
    ans*=i
    if ans>1000000000000000000:
        print(-1)
        sys.exit()
    else:
        continue
    
  if ans>1000000000000000000:
      print(-1)
  else:
      print(ans)
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
p = list(map(int,input().split()))
lstp = []
for i in range(n-k+1):
    lstp.append(0.5*(sum(p[i:i+k])+k))
print("{:.6f}".format(max(lstp)))

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
wa = sum(p[0:k])
next_wa = wa
for i in range(n-k):
    next_wa = next_wa - p[i] + p[i+k]
    if  next_wa > wa:
        wa = next_wa
print(0.5*(wa+k))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    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):
            L = j
            R = n
            ij = l[i] + l[j]
            while R - L != 1:
                if ij <= l[j + 1]:
                    break
                now = (L + R)//2
                if ij > l[now]: #三角形になる
                    L = now
                else:
                    R = now
            ans += L - j

    print(ans)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    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):
            L = j
            R = n
            ij = l[i] + l[j]
            while R - L != 1:
                if ij <= l[j + 1]:
                    break
                now = (L + R)//2
                if ij > l[now]: #三角形になる
                    L = now
                else:
                    R = now
            ans += L - j

    print(ans)

main()
### BUGGY CODE ###

s = input()
k = int(input())
anstr = ""
for i in range(len(s)):
  anstr += s[i]*(int(s[i])**5000000000000000)
print(anstr[k-1])

### FIXED CODE ###

s = input()
k = int(input())
ans = 1
for i in range(len(s)):
  if s[i] != "1":
    if i <= k-1:
      ans = int(s[i])
      break
print(ans)
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  all_count = H * W
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()


### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

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

N = int(input())
direction = list(input())
change = [0]*N

for i in range(N):
    for j in range(N):
        if j < i:
            if direction[j] != "E":
                change[i] += 1
        elif j > i:
            if direction[j] != "W":
                change[i] += 1

print(min(change))

### FIXED CODE ###

N = int(input())
direction = list(input())
change = [0]*(N+1)
# print(direction)
change[0] = direction.count("E")
# print(change)
for i in range(N):
    f_n = 0
    f_p = 0
    if direction[i] == "E":
        f_n = 1
    else:
        f_p = 1
    change[i+1] = change[i] - f_n + f_p
# print(change)
print(min(change))
### BUGGY CODE ###

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k  = map(int, input().split())
p  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

max_ = (sum(p[:k]), 0, k)
for i in range(n-k+1):
    if max_[0] < sum(p[i:i+k]):
        max_ = (sum(p[i:i+k]), i, i+k)

ans = 0
for p_ in p[max_[1]:max_[2]]:
    ans += 1 + (p_ - 1) * 0.5

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k  = map(int, input().split())
p  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

q = sum(p[:k])
max_ = (q, 0, k)
for i in range(k, n):
    q = q + p[i] - p[i-k]
    if max_[0] < q:
        max_ = (q, i-k+1, i+1)

ans = 0
for p_ in p[max_[1]:max_[2]]:
    ans += 1 + (p_ - 1) * 0.5

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

"""
二分探索

pythonでTLE, pypyでAC
"""

import sys
sys.setrecursionlimit(10**6)

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

L.sort()
ans = 0

for i in range(n-2):
    l_prev = 0
    for j in range(i+1,n-1):
        if not l_prev:
            l = j; r = n # 前のループで探索した範囲は探索不要なのでもっと高速化できるはず
        else:
            l = l_prev; r = n
        while l+1 < r:
            c = (l+r)//2
            if L[c] < L[i]+L[j]:
                l = c
            else:
                r = c
        ans += l-j
        l_prev = l
        
print(ans)

### FIXED CODE ###

"""二分探索"""

import sys
sys.setrecursionlimit(10**6)

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

L.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        l = j; r = n
        while l+1 < r:
            c = (l+r)//2
            if L[c] < L[i]+L[j]:
                l = c
            else:
                r = c
        ans += l-j
        
print(ans)