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

n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)

kougeki_start = 0
kougeki_end = 0
cnt = 0
for i in range(n):
    if h[i] > 0:
        left = i # 可能
        right = n # 不可能
        while left+1 < right:
            mid = (left + right) // 2
            if x[mid] - x[i] <= 2*d:
                left = mid
            else:
                right = mid
        cnt += h[i]
        hiku = h[i]
        for j in range(i, left+1):
            h[j] -= hiku

print(cnt)

### FIXED CODE ###

n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)

# 攻撃に巻き込めるインデックスを求める
left = 0 # 可能
right = n # 不可能
while left+1 < right:
    mid = (left + right) // 2
    if x[mid] - x[0] <= 2*d:
        left = mid
    else:
        right = mid
makikomi = [left]
right = left
for i in range(1, n):
    while x[right] - x[i] <= 2*d:
        right += 1
    right -= 1
    makikomi.append(right)

cnt = [0 for i in range(n)]
left = 0
already = 0
for i in range(n):
    while x[makikomi[left]] < x[i]:
        already -= cnt[left]
        left += 1
    cnt[i] = max(h[i] - already, 0)
    already += cnt[i]

print(sum(cnt))
### BUGGY CODE ###

import itertools

N = int(input())

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

edge = list(itertools.combinations(L,3))

con = 0

for i in range(0,len(edge)):
	edge[i] = list(edge[i])
	edge[i].sort(reverse = True)
	a = edge[i][0]
	b = edge[i][1]
	c = edge[i][2]
	if a < b + c:
		con += 1
		
print(con)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())

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

L.sort()

con = 0

for i in range(0,N):
  for j in range(i + 1,N):
    a = L[i]
    b = L[j]
    #a + bよりでかい最小の数のインデックス
    p = bisect_left(L,a + b)
    #cとbの間の区間を取る
    con += (p - 1) - j


print(con)
### BUGGY CODE ###

MAX_NUM = 10**6 + 1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ANSWER = 0
# Sの最大値をイテレート
for i in range(K-1, N):

    for j in range(i-K+2):
        ANSWER += (A[i]-A[j])*combinations(i-j+1-2, K-2)
        ANSWER %= MOD
print(ANSWER)


### FIXED CODE ###

MAX_NUM = 10**6 + 1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
N, K = map(int, input().split())
A = list(map(int, input().split()))
A=sorted(A)
ANSWER = 0
# Sの最大値をイテレート
for i in range(K-1, N):
    ANSWER += A[i]*combinations(i, K-1)
    # print(ANSWER)
for i in range(N-K+1):
    ANSWER -= A[i]*combinations(N-i-1, K-1)
    # print(ANSWER)

ANSWER %= MOD
print(ANSWER)
### BUGGY CODE ###

import math

if __name__ == '__main__':
    N = int(input())
    total = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                total += math.gcd(k, math.gcd(j, i))
    print(total)



### FIXED CODE ###

import math
from functools import lru_cache

@lru_cache(maxsize=10**6)
def cached_gcd(i, j):
    return math.gcd(i, j)

if __name__ == '__main__':
    N = int(input())
    total = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            g = cached_gcd(j, i)
            for k in range(1, N + 1):
                total += cached_gcd(k, g)
    print(total)
### BUGGY CODE ###

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

count=0

"""
for i in range(n):
    count+=a[i]//2
    a[i]=a[i]%2
"""

for i in range(n-1):
    while((a[i]>0) & (a[i+1]>0)):
        a[i]-=1
        a[i+1]-=1
        count = count+1

for i in range(n):
    count+=a[i]//2
    a[i]=a[i]%2

print(count)

### FIXED CODE ###

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

count=0

for i in range(n):
    if(a[i]>0):
        count+=(a[i]-1)//2
        a[i]=((a[i]-1))%2+1


for i in range(n-1):
    count+=a[i]//2
    a[i]=a[i]%2
    if((a[i]>0) & (a[i+1]>0)):
        MinNum=min(a[i],a[i+1])
        a[i]-=MinNum
        a[i+1]-=MinNum
        count = count+MinNum


count+=a[n-1]//2
a[n-1]=a[n-1]%2

print(count)
### BUGGY CODE ###

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

s = [0] * n
t = [0] * n

s[0] = a[0]
t[0] = a[0]

for i in range(1, n):
    s[i] = s[i-1] + a[i]
    t[i] = t[i-1] ^ a[i]

s = [0] + s
t = [0] + t 

ans = 0
#print(s, t)

l = 1
while l < n+1:
    r = l
    while True:
        #print(l, r, s[r] - s[l-1], t[r] ^ t[l-1])
        if s[r] - s[l-1] == t[r] ^ t[l-1] and r <= n:
            r += 1
            if r > n:
                ans += r - l
                break
        else:
            ans += r - l 
            break
    l += 1

print(ans)

### FIXED CODE ###

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

s = [0] * n
t = [0] * n

s[0] = a[0]
t[0] = a[0]

for i in range(1, n):
    s[i] = s[i-1] + a[i]
    t[i] = t[i-1] ^ a[i]

s = [0] + s
t = [0] + t 

ans = 0
#print(s, t)

l = 1
r = l
while l < n+1:
    #print(l, r)
    if s[r] - s[l-1] == t[r] ^ t[l-1]:
        while True:
            #print(l, r, s[r] - s[l-1], t[r] ^ t[l-1])
            if s[r] - s[l-1] == t[r] ^ t[l-1]:
                r += 1
                if r > n:
                    ans += r - l
                    r = n
                    break
            else:
                ans += r - l 
                break
    else:
        while True:
            #print(l, r, s[r] - s[l-1], t[r] ^ t[l-1])
            if s[r] - s[l-1] == t[r] ^ t[l-1]:
                ans += r - l + 1
                break
            else:
                r -= 1
                if r == l:
                    ans += 1
                    r = l + 1
                    break

    l += 1

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

n = int(input())

a = 1
b = 1
for i in range(-1000, 1000):
  for j in range(-1000, 1000):
    if ((i ** 5) - (j ** 5) == n):
      a = i
      b = j

print("%d %d" %(a, b))

### FIXED CODE ###

n = int(input())

a = 1
b = 1
for i in range(-200, 200):
  for j in range(-200, 200):
    if ((i ** 5) - (j ** 5) == n):
      a = i
      b = j

print("%d %d" %(a, b))
### BUGGY CODE ###

from heapq import heappush, heappop

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

rev_p = [0] * (n * n)
for offset in range(len(p)):
    rev_p[p[offset] - 1] = offset

ans = 0
for i, pi in enumerate(p):
    h = []
    heappush(h, (0, pi-1))
    memo = set()

    while h:
        cost, pos = heappop(h)

        if pos in memo:
            continue

        memo.add(pos)

        if pos < n or pos >= n * (n-1) or pos % n == 0 or pos % n == n-1:
            ans += cost
            break

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n * n:
                if rev_p[pos + offset] < i:
                    heappush(h, (cost, pos + offset))
                else:
                    heappush(h, (cost + 1, pos + offset))

print(ans)


### FIXED CODE ###

from collections import deque

n = int(input())
n2 = n * n
p = list(map(int, input().split()))

costs = [0] * n2

for i in range(n2):
    costs[i] = min(i // n, n - i // n - 1, i % n, n - i % n - 1)

remains = [1] * n2

ans = 0
for i, pi in enumerate(p):
    ans += costs[pi-1]
    remains[pi-1] = 0

    d = deque()
    d.append((pi-1, costs[pi-1]))

    while d:
        pos, cost = d.popleft()

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n2:
                next_cost = cost + remains[pos]

                if costs[pos+offset] > next_cost:
                    costs[pos+offset] = next_cost
                    d.append((pos+offset, next_cost))

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

import heapq

def dijkstra(s, edge):
    cost = [float('inf')] * n
    cost[s] = 0
    hq = [(0, s)]
    heapq.heapify(hq)
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]:
            continue
        for d, u in edge[v]:
            if c + d < cost[u]:
                heapq.heappush(hq, (c + d, u))
                cost[u] = c + d
    return cost

n, m, s, t = map(int, input().split())
s -= 1
t -= 1
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    yen[u].append((a, v))
    yen[v].append((a, u))
    snuuk[u].append((b, v))
    snuuk[v].append((b, u))
py = dijkstra(s, yen)
ps = dijkstra(t, snuuk)
idx = -1
for i in range(n):
    if idx < i:
        res, idx = min((py[j] + ps[j], j) for j in range(i, n))
    print(10 ** 15 - res)


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
    dist = [float('inf')] * N
    dist[s] = 0
    que = [(0, s)]
    heapq.heapify(que)
    while que:
        d, v = heapq.heappop(que)
        if d > dist[v]:
            continue
        for u, l in neighbor[v]:
            tmp_d = d + l
            if tmp_d < dist[u]:
                dist[u] = tmp_d
                heapq.heappush(que, (tmp_d, u))
    return dist

N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    snuuk[u-1].append((v-1, b))
    snuuk[v-1].append((u-1, b))

dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
    if dist_s[i] + dist_t[i] < tmp:
        tmp = dist_s[i] + dist_t[i]
    ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
### BUGGY CODE ###

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

H, W = list(map(int, input().split()))
all_count = H * W
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()
    for ch, cw in cands:
      nh, nw = i + ch, j + cw
      if nh < 0 or nh >= H or nw < 0 or nw >= W:
        continue
      if not L[nh][nw]:
        L[nh][nw] = True
        nq.append((nh, nw))
  
  if nq:
    q = copy.copy(nq)
  else:
    break    
    
  result += 1

print(result)

### 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 ###

#155c
import collections
n = int(input())
s = [input() for _ in range(n)]

c = collections.Counter(s)
ret = []
tmp = []

for k, v in c.most_common():
  if max(c.values()) == v:
    ret.append(k)
  else:
    break

for r in sorted(ret):
  print(r)


### FIXED CODE ###

#155c
import collections
n = int(input())
s = [input() for _ in range(n)]

c = collections.Counter(s)
ret = []
tmp = []
max_v = max(c.values())

for k, v in c.most_common():
  if max_v == v:
    ret.append(k)
  else:
    break

for r in sorted(ret):
  print(r)
### BUGGY CODE ###

import copy

H, W = map(int, input().split())
S = [[0 if c == '.' else 1 for c in input()] for _ in range(H)]

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

def bfs(y, x):
    q = [[y,x,0]]
    ST = copy.deepcopy(S)
    res = -1
    while len(q):
        ST[y][x] = 1
        y, x, d = q.pop(0);
        res = max(res, d)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= ny <= H-1 and 0 <= nx <= W-1): continue
            if ST[ny][nx] == 1: continue
            q.append([ny,nx,d+1])
    return res

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == 1: continue
        ans = max(ans, bfs(i,j))
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
INF = 10**9 + 7

def bfs(y, x):
    res = 0
    q = [[y,x]]
    D = [[INF for _ in range(W)] for _ in range(H)]
    D[y][x] = 0
    while len(q):
        y, x = q.pop(0);
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= ny <= H-1 and 0 <= nx <= W-1): continue
            if S[ny][nx] == '#': continue
            if D[ny][nx] > D[y][x] + 1:
                D[ny][nx] = D[y][x] + 1
                q.append([ny,nx])
                res = max(res, D[ny][nx])
    return res

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#': continue
        ans = max(ans, bfs(i,j))
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,T=map(int,input().split())
    A=[0]*N
    B=[0]*N
    for i in range(N):
        A[i],B[i]=map(int,input().split())
    A_argsorted=np.argsort(A)
    dp=[[0]*T for _ in range(N)]
    for i in range(N-1):
        for t in range(T-1):
            dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1])
            if t+1>=A[A_argsorted[i]]:
                dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1-A[A_argsorted[i]]]+B[A_argsorted[i]])
    ans=0
    B_sorted=[B[x] for x in A_argsorted]
    B_max=max(B_sorted)
    for i in range(1,N):
        if B_max==B_sorted[i-1]:
            B_max=max(B_sorted[i:])
        ans=max(ans,dp[i][T-1]+B_max)
    print(ans)
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,T=map(int,input().split())
    l=[]
    for i in range(N):
        A,B=map(int,input().split())
        l.append((A,B))
    l.sort()
    dp=[[0]*T for _ in range(N)]
    for i in range(N-1):
        for t in range(T-1):
            dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1])
            if t+1>=l[i][0]:
                dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1-l[i][0]]+l[i][1])
    ans=0
    B_sorted=[x[1] for x in l]
    for i in range(1,N):
        ans=max(ans,dp[i][T-1]+max(B_sorted[i:]))
    print(ans)
        

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

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    d=j-i
                    k=j+d
                    if k<n:
                        if s[k]!=s[j] and s[i]!=s[k]:
                            ans-=1
                        

      
print(ans)
        

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    d=j-i
                    k=j+d
                    if k<n:
                        if s[k]!=s[j] and s[i]!=s[k]:
                            ans-=1
                        

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

MOD=10**9+7

S=input()
N=len(S)
dp=[[0 for _ in range(13)] for _ in range(N)]
if S[0]=="?":
    for k in range(10):
        dp[0][k]=1
else:
    dp[0][int(S[0])]=1
for i in range(N-1):
    c=S[i+1]
    nums=[]
    if c=="?":
        nums=[i for i in range(10)]
    else:
        nums=[int(c)]
    for num in nums:
        for j in range(13):
            dp[i+1][(10*j+num)%13]+=dp[i][j]
print(dp[-1][5]%MOD)


### FIXED CODE ###

S=input()
dp=[[0 for _ in range(13)] for _ in range(len(S))]
MOD=10**9+7
if S[0]=='?':
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[0])]+=1
for i in range(1, len(S)):
  cur_nums=[i for i in range(10)] if S[i]=='?' else [int(S[i])]
  for cur in cur_nums:
    for rem in range(13):
      dp[i][(10*rem+cur)%13]=(dp[i][(10*rem+cur)%13]+dp[i-1][rem])%MOD
print(dp[-1][5])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
 
res=1
for i in A:
    print(A.count(res))
    res+=1
 
print(0)

### FIXED CODE ###

import collections
 
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
for i in range(1, N+1):
    print(cnt[i])
### BUGGY CODE ###

# ABC073 C - Write and Erase
# 2019/10/28

def main():
    N, *A = map(int, open(0).read().split())
#     print(N, A)
    set_A = list(set(A))
#     list_count = [A.count(i)%2 for i in set_A]
#     print(list_count)
#     print(sum(list_count))
    
    list_count = 0
    for i in set_A:
        list_count += A.count(i)%2
    print(list_count)
    
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter

def main():
    N, *A = map(int, open(0).read().split())
#     print(N, A)
    c = Counter(A)
#     print(c)

    print(sum(v & 1 for v in c.values()))

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

import math

def is_prime(n):
    for p in range(2, int(math.sqrt(n)) + 1):
        if n % p == 0:
            return False
    return True

A, B = map(int, input().split())
N = min(A, B) // 2
lst = [1]
for n in  range(2, N + 1):
    if A % n == 0 and B % n == 0:
        lst.append(n)

ret = 1
for n in lst[1:]:
    if is_prime(n):
        ret += 1
print(ret)

### FIXED CODE ###

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)
 
def prime_factorize(n):
    a = 2
    lst = []
    while a * a <= n:
        if n % a == 0:
            n = n / a
            lst.append(a)
        else:
            a += 1
    if n > 1:
        lst.append(n)
    return lst
 
A, B = map(int, input().split())
n = gcd(A, B)
lst = prime_factorize(n)
print(len(set(lst)) + 1)
### BUGGY CODE ###

A, B = map(int, input().split())
bin_nums = []
binB = bin(B)[2:]
for x in range(A, B+1):
    binx = bin(x)[2:]
    if len(binx) < len(binB):
        binx = '0' * (len(binB) - len(binx)) + binx
    bin_nums.append(binx)
ans = ''
for i in range(len(binB)):
    c1 = 0
    for j in range(len(bin_nums)):
        if bin_nums[j][i] == '1':
            c1 += 1
    if c1 % 2 == 0:
        ans += '0'
    else:
        ans += '1'
print(int(ans, 2))


### FIXED CODE ###

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


def xor(n):
    m = 0
    if n % 4 == 0:
        m = n
    elif n % 4 == 1:
        m = 1
    elif n % 4 == 2:
        m = n + 1
    return m


p = xor(A-1)
q = xor(B)
print(p ^ q)
### BUGGY CODE ###

def solve():
  n = int(input())
  s = input()
 
  ans = 10**15
  for i in range(n+1):
   s1 = s[0:i]
   s2 = s[i::]
   tp = s1.count('#')
   tp2 = s2.count(".")
   ans = min(ans,tp+tp2)
  print(ans)
solve()

### FIXED CODE ###

def solve():
  n = int(input())
  s = input()
  
  leftblack = 0
  leftwhite = 0
  rightblack = s.count('#')
  rightwhite = s.count(".")
  
  ans = leftblack+rightwhite
  
  for i in range(n):
    if s[i] == "#":
      leftblack += 1
      rightblack -= 1
    else:
      leftwhite += 1
      rightwhite -= 1
    ans = min(ans,leftblack+rightwhite)
  
  print(ans)
solve()
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
p, q, r = cnt[1], cnt[2], cnt[3]


def memo_dp(dp_list, i, j, k):
    if (i < 0) or (j < 0) or (k < 0):
        return 0
    if dp_list[i][j][k] != -1:
        return dp_list[i][j][k]
    else:
        pt1 = i * memo_dp(dp_list, i - 1, j, k)
        pt2 = j * memo_dp(dp_list, i + 1, j - 1, k)
        pt3 = k * memo_dp(dp_list, i, j + 1, k - 1)
        dp_list[i][j][k] = (n + pt1 + pt2 + pt3) / (i + j + k)
        return dp_list[i][j][k]


dp = [[[-1] * (301) for _ in range(301)] for _ in range(301)]
dp[0][0][0] = 0

ans = memo_dp(dp, p, q, r)
print(ans)


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = [0,0,0]
for x in LI():
    a[x-1] += 1
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(a[2]+1):
    for j in range(a[1]+a[2]+1):
        for i in range(N+1):
            if not (0 < i+j+k <= N): continue
            x = 0.0
            if i > 0: x += dp[i-1][j][k] * (i/N)
            if j > 0: x += dp[i+1][j-1][k] * (j/N)
            if k > 0: x += dp[i][j+1][k-1] * (k/N)
            x += 1.0
            x *= N / (i+j+k)
            dp[i][j][k] = x
print(dp[a[0]][a[1]][a[2]])
### BUGGY CODE ###

n = int(input())
a_list = [int(i) for i in input().split(' ')]
total = [a_list[0]]
counter = 0

for a in a_list[1:]:
    total.append(total[-1] + a)
    
if total[0]==0:
    total = list(map(lambda n: n-int(total[1]/abs(total[1])), total))
for i in range(1,n):    
    if total[i-1]<0 and total[i]<=0:
        counter += abs(total[i])+1
        total[i:] = list(map(lambda n: n-(total[i])+1, total[i:]))
    elif total[i-1]>0 and total[i]>=0:
        counter += abs(total[i])+1
        total[i:] = list(map(lambda n: n-(total[i])-1, total[i:]))
    else:
        continue

print(counter)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split(' ')]
_a = [-1*i for i in a]

def func(l):
    _ans = 0
    product = 0
    for i in range(n):
        product += l[i]
        if i%2 == 0:
            if product<=0:
                _ans += abs(product) + 1
                product = 1
        elif i%2 == 1:
            if product>=0:
                _ans += abs(product) + 1
                product = -1
    return _ans

ans = min(func(a), func(_a))
print(ans)
### BUGGY CODE ###

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



done = []
light = 0
flag = 0
ans = -1
cnt = 0

while flag == 0:
  done.append(light)
  light = A[light]
  cnt += 1

  if light == 1:
    ans = cnt
    flag = 1
  if light in done:
    flag = 1
print(ans)

### FIXED CODE ###

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

light = 0
ans = -1
for n in range(1,N+1):
  light = A[light]
  if light ==1:
    ans = n
    break
print(ans)