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

N = int(input())
light_rule = {n:int(input())-1 for n in range(N)}

light = ["1"]+["0"]*(N-1)
target = ["0"]+["1"]+["0"]*(N-2)
searched = {"".join(light):1}

flag = 0
num = 0
bottun = 0
while True:
    if light == target:
        flag = 1
        break
    num += 1
    # print(bottun, light_rule[bottun])
    light[bottun] = "0"
    light[light_rule[bottun]] = "1"
    bottun = light_rule[bottun]
    # print(light)
    if searched.get("".join(light)):
        break
    else:
        searched["".join(light)] = 1
    
if flag:
    print(num)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
light_rule = {n:int(input())-1 for n in range(N)}

light = ["1"]+["0"]*(N-1)

flag = 0
num = 0
bottun = 0
for _ in range(N):
    if light[1] == "1":
        flag = 1
        break
    num += 1
    # print(bottun, light_rule[bottun])
    light[bottun] = "0"
    light[light_rule[bottun]] = "1"
    bottun = light_rule[bottun]
    # print(light)
    
if flag:
    print(num)
else:
    print(-1)
### BUGGY CODE ###

def main():
    N,M=map(int,input().split())
    H=[int(_) for _ in input().split()]
    near=[[i] for i in range(N)]
    flag=[i for i in range(N)]
    AB=[]
    for m in range(M):
        ab=list(map(int,input().split()))
        if ab not in AB:
            AB.append(ab)
    for A,B in AB:
        near[A-1].append(B-1)
        near[B-1].append(A-1)
    ans=0
    for n in near:
        k=1
        for j in n[1:]:
            if H[n[0]] <= H[j]:
                k=0
        if k:
            ans+=1
    print(ans)

main()

### FIXED CODE ###

def main():
    N,M=map(int,input().split())
    H=[int(_) for _ in input().split()]
    near=[[i] for i in range(N)]
    flag=[i for i in range(N)]
    for m in range(M):
        A,B=map(int,input().split())
        near[A-1].append(B-1)
        near[B-1].append(A-1)
    ans=0
    for n in near:
        k=1
        for j in n[1:]:
            if H[n[0]] <= H[j]:
                k=0
        if k:
            ans+=1
    print(ans)

main()
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[None for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
DP[0][0][0] = 0
def dp(i, j, k):
    if i < 0 or j < 0 or k < 0:
        return 0
    if DP[i][j][k] != None:
        return DP[i][j][k]
    DP[i][j][k] = (n+dp(i-1, j, k)*i+dp(i+1, j-1, k)*j+dp(i, j+1, k-1)*k)/(i+j+k)
    return DP[i][j][k]
print(dp(a, b, c))


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])
### BUGGY CODE ###

import os, sys, re, math


(H, W) = [int(n) for n in input().split()]


def set_moves(x, y, moves):
    if S[y + 1][x + 1] != '.':
        return
    if 0 <= grid[y][x] < moves:
        return

    grid[y][x] = moves
    set_moves(x, y - 1, moves + 1)
    set_moves(x, y + 1, moves + 1)
    set_moves(x - 1, y, moves + 1)
    set_moves(x + 1, y, moves + 1)


S = []
S.append('#' * (W + 2))
for i in range(H):
    S.append('#' + input() + '#')
S.append('#' * (W + 2))

result = 0
for gy in range(H):
    for gx in range(W):
        if S[gy + 1][gx + 1] != '.':
            continue
        grid = []
        for i in range(H):
            grid.append([-1] * W)
        set_moves(gx, gy, 0)

        result = max(result, max([max(row) for row in grid]))

print(result)


### FIXED CODE ###

import os, sys, re, math


(H, W) = [int(n) for n in input().split()]


def set_moves(x, y, moves):
    if S[y + 1][x + 1] != '.':
        return
    if 0 <= grid[y][x] < moves:
        return

    grid[y][x] = moves
    set_moves(x, y - 1, moves + 1)
    set_moves(x, y + 1, moves + 1)
    set_moves(x - 1, y, moves + 1)
    set_moves(x + 1, y, moves + 1)


S = []
S.append('#' * (W + 2))
has_wall = False
for i in range(H):
    s = input()
    has_wall |= '#' in s
    S.append('#' + s + '#')
S.append('#' * (W + 2))

if not has_wall:
    result = W + H - 2
else:
    result = 0
    for gy in range(H):
        for gx in range(W):
            if S[gy + 1][gx + 1] != '.':
                continue
            grid = []
            for i in range(H):
                grid.append([-1] * W)
            set_moves(gx, gy, 0)

            result = max(result, max([max(row) for row in grid]))

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

N = int(input())
def divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
    
ans = 0
for k in range(1, N+1):
    ans += k*divisors(k)

print(ans)

### FIXED CODE ###

N = int(input())
A = [0]*(N+1)
for i in range(1, N+1):
  for j in range(i, N+1, i):
    A[j] += j
print(sum(A))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000 * 1000)

h, w, a, b = map(int, input().split())


def check_mat(m):
    # print()
    # print(m)
    zeros_h = [0] * w

    for i in range(h):
        zeros_w = 0
        for j in range(w):
            if m[i][j] == 0:
                zeros_w += 1
                zeros_h[j] += 1

        if min(zeros_w, w - zeros_w) != a:
            return 0
    # print(zeros_h)
    for i in range(w):
        if min(zeros_h[i], h - zeros_h[i]) != b:
            return 0
    return 1


def check(l, cnt):
    if cnt == h * w:
        mm = []
        for i in range(h):
            mm.append([])
            for j in range(w):
                mm[-1].append(l[i * w + j])
        if check_mat(mm) == 1:
            return mm
        else:
            return None
    mm1 = check(l + [1], cnt + 1)
    if mm1:
        return mm1
    mm2 = check(l + [0], cnt + 1)
    if mm2:
        return mm2


mm = check([], 0)

for i in range(h):
    for j in range(w):
        print(mm[i][j], end='')
    print()


### FIXED CODE ###

h, w, a, b = map(int, input().split())

ans = []

for i in range(h):
    ans.append([])
    for j in range(w):
        if i < b and j < a:
            ans[i].append(0)
        elif i >= b and j >= a:
            ans[i].append(0)
        else:
            ans[i].append(1)

for i in range(h):
    for j in range(w):
        print(ans[i][j], end='')
    print()
### BUGGY CODE ###

#MLE注意！ not は使わず !=
#0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = input().rstrip()
    res = [0]*2019
    res[0] += 1
    
    for i in range(len(n)):
        a = int(n[i:])
        b = a%2019
        res[b] += 1
    ans = 0
    for i in res:
        if i>=2:
            ans += i*(i-1)//2
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#MLE注意！ not は使わず !=
#0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = input().rstrip()
    n = n[::-1]
    res = [0]*2019
    res[0] += 1
    b = 1
    c = 0
    for i in range(len(n)):
        a = int(n[i])
        c += a*b
        c %= 2019
        res[c] += 1
        b = b*10%2019
    ans = 0
    for i in res:
        if i>=2:
            ans += i*(i-1)//2
    print(ans)

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

N = int(input())
a = [int(i) for i in input().split()]
A = 1
if 0 in a:
    A = 0
else:
    for i in range(N):
        A = A * a[i]
        if A > 10**18:
            A = -1

print(A)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
A = 1
if 0 in a:
  print(0)
  exit()
for i in range(N):
  A = A * a[i]
  if A > 1000000000000000000:
    print(-1)
    exit()
print(A)
### BUGGY CODE ###

S = input()
Q = int(input())
q_list = []
for i in range(Q):
    q_list.append(input().split(" "))
    if q_list[i][0] == "1":
        S = S[::-1]
    elif q_list[i][1] == "1":
        S = q_list[i][2] + S
    else :
        S = S + q_list[i][2]
print(S)


### FIXED CODE ###

S = input()
Q = int(input())
top_str = ""
last_str = ""
s_parity = 0
for i in range(Q):
    q_list=input().split(" ")
    if q_list[0] == "1":
        s_parity += 1
    elif (s_parity%2) == 0:
        if q_list[1] == "1":
            top_str = q_list[2] + top_str
        else:
            last_str = last_str + q_list[2]
    else:
        if  q_list[1] == "1":
            last_str = last_str + q_list[2]
        else:
            top_str = q_list[2] + top_str


if s_parity % 2 ==1:
    S = S[::-1]
    S = last_str[::-1] + S + top_str[::-1]
else :
    S = top_str + S + last_str
print(S)
### BUGGY CODE ###

from queue import Queue

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

oriented = [[] for i in range(N)]
or_cop = [[] for i in range(N)]
oriented_num=[0 for i in range(N)]
oriented_tf = [False for i in range(N)]
to = [[] for i in range(N)]
to_num=[0 for i in range(N)]

for i in range(N-1+M):
    a,b=list(map(int,input().split()))
    a=a-1
    b=b-1
    oriented[b].append([a,to_num[a]])
    or_cop[b].append([a,to_num[a]])
    to[a].append([b,oriented_num[b]])
    oriented_num[b]+=1
    to_num[a]+=1
    oriented_tf[b]=True

for i in range(N):
    if oriented_tf[i]==False:
        root=i
        break

q = Queue()
q.put(root)
L = []

while not q.empty():
    v=q.get()
    L.append(v)
    for i in range(len(to[v])):
        m=to[v][i][0]
        d=to[v][i][1]
        to[v][i][0]=-1
        oriented[m][d][0]=-1
        flag=True
        for u in oriented[m]:
            if u[0]!=-1 and u[0]!=v:
                flag=False
                break
        if flag:
            q.put(m)

LL= [[L[i],i] for i in range(N)] 

LL=sorted(LL,key=lambda x: x[0])

for i in range(N):
    i_max=-1
    pare = -1
    if i==root:
        print(0)
    else:
        for cand in or_cop[i]:
            if LL[cand[0]][1]>i_max:
                i_max=LL[cand[0]][1]
                pare=cand[0]
        print(pare+1)

### FIXED CODE ###

from collections import defaultdict, deque

N, M = map(int, input().split())
v = N
n = N+M-1
es = [[int(x)-1 for x in input().split()] for _ in range(n)]
or_cop = [[] for i in range(N)]
for e in es:
    or_cop[e[1]].append(e[0])

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
root=res[0]            
LL = [[res[i],i] for i in range(N)]

LL=sorted(LL,key=lambda x: x[0])

for i in range(N):
    i_max=-1
    pare = -1
    if i==root:
        print(0)
    else:
        for cand in or_cop[i]:
            if LL[cand][1]>i_max:
                i_max=LL[cand][1]
                pare=cand
        print(pare+1)
### BUGGY CODE ###

import sys
import math
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N = readint()
    for i in range(1, N + 1):
        s = math.ceil(math.sqrt(i))
        ans = 0
        for j in range(1, s):
            for k in range(1, s):
                l = s - j - k
                if l <= 0:
                    break
                else:
                    if j * k + k * l + j * l == s ** 2 - i:
                        ans += 1

        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N = readint()

    ans = {i: 0 for i in range(1, 20000)}
    for i in range(3, 124):
        for j in range(1, i):
            for k in range(1, i):
                l = i - j - k
                if l <= 0:
                    break
                else:
                    v = j ** 2 + k ** 2 + l ** 2 + j * k + k * l + j * l
                    ans[v] += 1
    for i in range(1, N + 1):
        print(ans[i])


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

n, k, q = map(int,input().split())
a = [int(input()) for i in range(q)]
point = [k]*n

for i in range(len(a)):
  for j in range(len(point)):
    if a[i] == j+1:
      continue
    point[j] -= 1
for b in range(len(point)):
  if point[b] <= 0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

n, k, q = map(int,input().split())
points = [k-q]*n

for i in range(q):
  m = int(input())
  points[m-1] = points[m-1] + 1

for j in range(len(points)):
  if points[j] <= 0:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def divide(x): #約数配列
    div=[]
    for check in range(1,int(x**0.5)+1):
        if(x%check==0):
            div.append(check)
            div.append(x//check)
    div.sort()
    return div

def main():
    n = inp()
    a = inpl()
    dic = defaultdict(int)
    a.sort()
    ans = 0
    for i in range(n):
        div = divide(a[i])
        flag = 1
        for e in div:
            if dic[e]:
                flag = 0
                break
        if i < n-1 and a[i] == a[i+1]:
            flag = 0
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    N = max(a)+1
    tab = [1 for _ in range(N)]
    for i in range(n):
        x = a[i]
        if i < n-1 and a[i] == a[i+1]:
            tab[a[i]] = 0
        if tab[x]:
            ans += 1
        for i in range(N):
            if x*i >= N:
                break
            tab[x*i] = 0        
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from heapq import heappush, heappop
import itertools
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[100000000000000000000 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))
while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse = True)
c = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            if l[j] + l[k] > l[i]:
                c += 1
print(c)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()
c = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):   
        c += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(c)
### BUGGY CODE ###

N, K = map(int, input().split())
a = []
for i in range(N):
    x, y = map(int, input().split())
    for j in range(y):
        a.append(x)
a.sort()

print(a[K - 1])

### FIXED CODE ###

N, K = map(int, input().split())
a = []
b = []
Sum = 0
for i in range(N):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)
s = [*range(len(a))]
sort_s = sorted(s, key = lambda i: a[i])
sort_a = [a[i] for i in sort_s]
sort_b = [b[i] for i in sort_s]
for i in range(N):
    Sum += sort_b[i]
    if Sum >= K:
        print(sort_a[i])
        break
### BUGGY CODE ###

##C
n = int(input())
a = list(map(int,input().split()))
b = list()
for i in range(n):
    for j in range(n):
        if a[j] == i+1:
            b.append(j+1)
print(*b)

### FIXED CODE ###

##C
n = int(input())
a = list(map(int,input().split()))
##リストに0をn個いれておく
b = [0]*n
##enumerateで、要素とインデックスを両方得る
for i , val in enumerate(a):
    b[val-1] = i+1
print(*b)
### BUGGY CODE ###

n = int(input())
nums = list(map(int, input().split()))
result = []

minNum = min(nums)
while(len(result) != n):
    result.append(str(nums.index(minNum) + 1))
    nums[nums.index(minNum)] = 10**5 + 1
    minNum += 1

print((" ").join(result))

### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
pairlist = []
for i in range(len(nums)):
    pairlist.append([i, nums[i]])

sortedPairList = sorted(pairlist, key=lambda item: item[1])

result = []
for i in sortedPairList:
    result.append(str(i[0]+1))
print(" ".join(result))
### BUGGY CODE ###

from bisect import bisect,bisect_left
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = [0]*29
for k in range(29):
    ans[k] = 0

for b in B:
    for k in range(29):
        b_k = b%(2**(k+1))
        a = sorted([a%(2**(k+1)) for a in A])
        ans[k] += bisect(a,2**(k+1)-1-b_k)-bisect_left(a,2**k-b_k)
        ans[k] += N-bisect_left(a,3*2**k-b_k)
        ans[k] %= 2

print(sum([ans[k]*2**k for k in range(29)]))

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.int32(input().split())
B = np.int32(input().split())

ans_arr = np.zeros(29,int)
for k in range(29):
    a = np.sort(A%(2**(k+1)))
    b = B%(2**(k+1))
    ans_arr[k] += np.sum(np.searchsorted(a,2**(k+1)-1-b,side='right')-np.searchsorted(a,2**k-b))
    ans_arr[k] += np.sum(N-np.searchsorted(a,3*2**k-b))
    ans_arr[k] %= 2

ans = 0
for k in range(29):
    ans += ans_arr[k]*2**k

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

def main():
    r1, c1, r2, c2 = map(int, raw_input().split())
    MOD = 10 ** 9 + 7
    
    
    # 階乗 & 逆元計算
    factorial = [1]
    inverse = [1]
    for i in range(1, r2 + c2 + 10):
        factorial.append(factorial[-1] * i % MOD)
        inverse.append(pow(factorial[-1], MOD - 2, MOD))
    
    
    # 組み合わせ計算
    def nCr(n, r):
        if n < r or r < 0:
            return 0
        elif r == 0:
            return 1
        return factorial[n] * inverse[r] * inverse[n - r] % MOD
    
    
    ans = 0
    for r in range(r1, r2 + 1):
        ans += ((nCr(r + c2 + 1, r + 1) % MOD) - (nCr(r + c1, r + 1) % MOD)) % MOD
        ans %= MOD
    
    print(ans % MOD)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    r1, c1, r2, c2 = map(int, raw_input().split())
    MOD = 10 ** 9 + 7

    mod = 10 ** 9 + 7  # 出力の制限
    N = 10 ** 4
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

    for i in range(2, r2 + c2 + 10):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    def cmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return g1[n] * g2[r] * g2[n - r] % mod


    ans = 0
    for r in range(r1, r2 + 1):
        ans += ((cmb(r + c2 + 1, r + 1, MOD) % MOD) - (cmb(r + c1, r + 1, MOD) % MOD)) % MOD
        ans %= MOD

    print(ans % MOD)


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

def popcount(n):
    cnt = 0
    for i in range(n):
        if ((n >> i) & 1):
            cnt +=1
    return cnt

def f(n):
    cnt = 1
    while True:
        if n == 0:
            break
        n = n % bin(n).count('1')
        cnt += 1
    return cnt

def pow(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def numChange(list, num):
    i = len(list) - 1
    j = 0
    ans = 0
    while i >= 0:
        if list[i] == '1':
            ans += num[j]
        i -= 1
        j += 1
    return ans

if __name__ == "__main__":
    n = int(input())
    x = list(input())
    d = sum([y == '1' for y in x])
    num = []
    a = 1
    for i in range(n):
        num.append(a)
        a *= 2
    xNum = numChange(x, num)
    for i in range(n):
        if x[i] == "1":
            wk = xNum - num[len(x) - i - 1]
            wkd = d - 1
        else:
            wk = xNum + num[len(x) - i - 1]
            wkd = d + 1
        if wk == 0:
            print(0)
        else:
            wk %= wkd
            if wk == 0:
                print(1)
            else:
                print(f(wk))


### FIXED CODE ###

def f(n):
    cnt = 1
    while n > 0:
        n  %= bin(n).count('1')
        cnt += 1
    return cnt

if __name__ == "__main__":
    n = int(input())
    x = input()
    d = x.count('1')
    if d == 1:
        for i in x[:-1]:
            if i == '0':
                print(1)
            else:
                print(0)
        if x[-1] == '1':
            print(0)
        else:
            print(2)
        exit()

    ans = []
    M = 0
    for i in x:
        M <<= 1
        if i == '1':
            M += 1
    p = M % (d + 1)
    m = M % (d - 1)
    for i in range(n):
        if x[i] == '0':
            ans.append(f((p + pow(2, n - i - 1, d + 1)) % (d + 1)))
        else:
            ans.append(f((m - pow(2, n - i - 1, d - 1)) % (d - 1)))
    print(*ans, sep='\n')
### BUGGY CODE ###

import sys
input  = sys.stdin.readline

S = input()
N = len(S)

while True:
  n = len(S)
  S = S.replace('10','')
  if n == len(S):
    break
while True:
  n = len(S)
  S = S.replace('01','')
  if n == len(S):
    break
print(N-len(S))


### FIXED CODE ###

S = input()

c0=0
c1=0
for i in S:
  if i == '0':
    c0+=1
  else:
    c1+=1

print(2*min(c0,c1))