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

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
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():
    def dfs(u,s=0):
        route[u]=True
        memo[u]=s
        for v,c in ot[u]:
            if route[v]:
                if s+c>memo[v]:
                    return True
                continue
            if dfs(v,s+c):return True
            score[u]=max(score[u],score[v]+c)
        route[u]=False
        return False

    inf = 10 ** 14
    n, m = MI()
    ot = defaultdict(list)
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ot[b].append([a, c])

    score = [-inf] * n
    memo = [0] * n
    score[0]=0
    route=[False]*n
    if dfs(n-1):
        print("inf")
    else:
        print(score[n-1])

main()


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
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():
    inf = 10 ** 14
    n, m = MI()
    ee = []
    # スコアの正負を逆にし、最小値を求める問題に置き換える
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ee.append([a, b, -c])
    # ベルマン・フォードで最小スコアを計算
    # n-1回やっても更新があるということは負の閉路があるということ
    # 負の閉路がなければ答えを出力して終了
    score = [inf] * n
    score[0] = 0
    for _ in range(n):
        change = False
        for a, b, c in ee:
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                change = True
        if not change:
            print(-score[n - 1])
            exit()
    # 負の閉路がある場合は、その影響がゴールまで届くかをチェック
    reachable = [False] * n
    for _ in range(n):
        for a, b, c in ee:
            if reachable[a]:reachable[b]=True
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                reachable[b] = True
        if reachable[n - 1]:
            print("inf")
            exit()
    print(-score[n-1])

main()
### BUGGY CODE ###

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

ans = []
for i in range(1, N + 1):
    ans.append(A.index(i) + 1)

print(*ans)


### FIXED CODE ###

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

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

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

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

Rindexes = [i for i, x in enumerate(S) if x == 'R']
Gindexes = [i for i, x in enumerate(S) if x == 'G']
Bindexes = [i for i, x in enumerate(S) if x == 'B']
count = 0

# rgb
for i in Rindexes:
  for j in filter(lambda j: i < j, Gindexes):
    count += len(list(filter(lambda k: j < k and j - i != k - j, Bindexes)))
# rbg
for i in Rindexes:
  for j in filter(lambda j: i < j, Bindexes):
    count += len(list(filter(lambda k: j < k and j - i != k - j, Gindexes)))
# grb
for i in Gindexes:
  for j in filter(lambda j: i < j, Rindexes):
    count += len(list(filter(lambda k: j < k and j - i != k - j, Bindexes)))
# gbr
for i in Gindexes:
  for j in filter(lambda j: i < j, Bindexes):
    count += len(list(filter(lambda k: j < k and j - i != k - j, Rindexes)))
# brg
for i in Bindexes:
  for j in filter(lambda j: i < j, Rindexes):
    count += len(list(filter(lambda k: j < k and j - i != k - j, Gindexes)))
# bgr
for i in Bindexes:
  for j in filter(lambda j: i < j, Gindexes):
    count += len(list(filter(lambda k: j < k and j - i != k - j, Rindexes)))
print(count)

### FIXED CODE ###

N = int(input())
S = input()
rcount = 0
gcount = 0
bcount = 0
for i in range(N):
  if S[i] == 'R':
    rcount += 1
  elif S[i] == 'G':
    gcount += 1
  elif S[i] == 'B':
    bcount += 1

total = rcount * gcount * bcount
count = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2*j - i
    if k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
      count += 1
print(total - count)
### BUGGY CODE ###

from collections import Counter

s = input()
mod1 = 673
mod2 = 3

num1 = 0
num2 = 0
li1 = []
li2 = []
pw = 10
for i, e in enumerate(s, 1):
    num1 *= 10
    num1 += int(e)
    num1 %= mod1
    inv = pow(pw, mod1 - 2, mod1)
    li1.append(num1 * inv % mod1)

    num2 *= 10
    num2 += int(e)
    num2 %= mod2
    inv = pow(pw, mod2 - 2, mod2)
    li2.append(num2 * inv % mod2)

    pw *= 10

li = [0] + [10 * e1 + e2 for e1, e2 in zip(li1, li2)]
c = Counter(li)

ans = 0
for v in c.values():
    ans += v * (v - 1) // 2

print(ans)


### FIXED CODE ###

from collections import Counter

s = input()
mod1 = 673
mod2 = 3

num1 = 0
num2 = 0
li1 = []
li2 = []
pw1 = 10
pw2 = 10
for i, e in enumerate(s, 1):
    num1 *= 10
    num1 += int(e)
    num1 %= mod1
    inv = pow(pw1, mod1 - 2, mod1)
    li1.append(num1 * inv % mod1)

    num2 *= 10
    num2 += int(e)
    num2 %= mod2
    inv = pow(pw2, mod2 - 2, mod2)
    li2.append(num2 * inv % mod2)

    pw1 *= 10
    pw1 %= mod1
    pw2 *= 10
    pw2 %= mod2

li = [0] + [10 * e1 + e2 for e1, e2 in zip(li1, li2)]
c = Counter(li)

ans = 0
for v in c.values():
    ans += v * (v - 1) // 2

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

uf = UnionFind(N)
for i in range(M):
    A,B=map(int,input().split())
    uf.union(A-1,B-1)
    
dic=uf.all_group_members()

print(max([len(d) for d in dic.values()]))

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

uf = UnionFind(N)

for i in range(M):
    A,B=map(int,input().split())
    uf.union(A-1,B-1)

print(max([uf.size(i) for i in range(N)]))
### BUGGY CODE ###

s = input()
f = s
while True:
    s = s.replace('10', '')
    s = s.replace('01', '')
    t = list(s)
    if all(map(lambda x:x=="1", t)):
        break
    if all(map(lambda x:x=="0", t)):
        break
print(len(f)-len(s))

### FIXED CODE ###

s = input()
one = s.count('1')
zero = s.count('0')

print(min(one, zero)*2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

for i in range(n):
    l=a[:i]+a[i+1:]
    print(max(l))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=[0]*n
for i in range(n):
    a[i]=int(input())
b=sorted(a)

for i in range(n):
    if a[i]!=b[-1]:
        print(b[-1])
    else:
        print(b[-2])
### BUGGY CODE ###

n,m,k = map(int, input().split())
a = [0]+list(map(int, input().split()))
b = [0]+list(map(int, input().split()))

Goukei_a=[a[0]]
for i in range(1,n+1):
    Goukei_a.append(Goukei_a[i-1]+a[i])

Goukei_b=[b[0]]
for i in range(1,m+1):
    Goukei_b.append(Goukei_b[i-1]+b[i])

goukei=0
kaisuu=0
ans=0

for i in range(0,n+1):
    for j in range(0,m+1):
        goukei=Goukei_a[i]+Goukei_b[j]
        if goukei<=k:
            ans=max(ans,i+j)
        else:
            break
    
print(ans)

### FIXED CODE ###

n,m,k = map(int, input().split())

a = [0]+list(map(int, input().split()))
b = [0]+list(map(int, input().split()))

for i in range(1,n+1):
    a[i]+=a[i-1]
for i in range(1,m+1):
    b[i]+=b[i-1]

b_cnt=m
ans=0

for a_cnt in range(n+1):
    if a[a_cnt]>k:
        break
    while a[a_cnt]+b[b_cnt]>k:
         b_cnt-=1
    ans=max(ans,a_cnt+b_cnt)

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

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	A = [int(input()) for _ in range(N)]
	print(max(A[1:]))
	for i in range(1, N-1):
		print(max(max(A[:i]), max(A[i+1:])))
	print(max(A[:N]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	import sys
	import numpy as np
	input = sys.stdin.readline
	N = int(input())
	A = [int(input()) for _ in range(N)]
	A = np.array(A)
	maxNum = np.max(A)
	maxIndex = np.where(A == A.max())[0]
	if len(maxIndex) > 1:
		for _ in range(N):
			print(maxNum)
	elif maxIndex[0] == 0:
		print(np.max(A[1:]))
		for i in range(1, N):
			print(maxNum)
	elif maxIndex[0] == N-1:
		for i in range(N-1):
			print(maxNum)
		print(np.max(A[:N-1]))
	else:
		for i in range(maxIndex[0]):
			print(maxNum)
		prev = max(np.max(A[:maxIndex[0]]), np.max(A[maxIndex[0]+1:]))
		print(prev)
		for i in range(maxIndex[0]+1, N):
			print(maxNum)



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

N, M = map(int, input().split())
p = list()
d = dict()
for i in range(M):
    inp = list(map(int, input().split()))
    p.append(inp)
    if inp[0] in d:
        d[inp[0]].append(inp[1])
    else:
        d[inp[0]] = [inp[1]]
for i in d:
    d[i].sort()
for i, j in p:
    print("{:06d}{:06d}".format(i, d[i].index(j)+1))

### FIXED CODE ###

N, M = map(int, input().split())
p = [[] for i in range(M)]
counter = [0] * N
ans = [""] * M

for i in range(M):
    k, y = map(int, input().split())
    p[i] = [k, y, i]

p.sort(key=lambda x:x[1])
for k, y, i in p:
    counter[k-1] += 1
    ans[i] = "{:06d}{:06d}".format(k, counter[k-1])

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

n = int(input())
i = 1

while True:
    x = i
    if  x % 3 == 0 or x % 10 ==3 or x / 10 == 0:
        print(" " + i)
        i+=1
        if i > n:
            print()
            break


### FIXED CODE ###

#
# 5d
#

def main():
    n = int(input())
    s = ""
    for i in range(1, n+1):
        x = i
        if x % 3 == 0 or x % 10 == 3:
            s += " " + str(i)
        else:
            x //= 10
            while x:
                if x % 10 == 3:
                    s += " " + str(i)
                    break
                x //= 10
    print(s)


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

import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

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

def less(x):
    res = 0
    for i in range(N):
        e = A[i]
        if e < 0:
            res += i - bisect_right(A, x // e, 0, i)
        elif e > 0:
            res += bisect_left(A, - (- x // e), 0, i)
        elif x > 0:
            res += i
    return res

l = - (10 ** 18 + 1)
r = - l
while l + 1 < r:
    m = (l + r) // 2
    if less(m) < K:
        l = m
    else:
        r = m
print(l)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

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

neg = bisect_left(A, 0)
pos = bisect_right(A, 0)

def less(x):
    res = 0
    b = 0
    for i in range(0, neg):
        while b != N and A[i] * A[b] >= x:
            b += 1
        while b != 0 and A[i] * A[b - 1] < x:
            b -= 1
        res += max(i - b, 0)
    for i in range(neg, pos):
        if x > 0:
            res += i
    for i in range(pos, N):
        while b != N and A[i] * A[b] < x:
            b += 1
        while b != 0 and A[i] * A[b - 1] >= x:
            b -= 1
        res += min(b, i)
    return res

l = - (10 ** 18 + 1)
r = - l
while l + 1 < r:
    m = (l + r) // 2
    if less(m) < K:
        l = m
    else:
        r = m
print(l)
### BUGGY CODE ###

x=input().split()
h=int(x[0])
n=int(x[1])
a=[]
b=[]
for k in range(n):
  x=input().split()
  a.append(int(x[0]))
  b.append(int(x[1]))  
m=max(a)  
dp=[10**8]*(h+m)
dp[0]=0
for k in range(h+m):
  for i in range(n):
    if k-a[i]<0:
      continue
    if dp[k-a[i]]==10**8:
      continue
    new=dp[k-a[i]]+b[i]
    if new < dp[k]:
      dp[k]=new
print(min(dp[h:h+m]))
      
      
  

  
      

### FIXED CODE ###

x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=(dp[k-a]+b).min()
print(dp[h:h+m].min())
### BUGGY CODE ###

n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]
dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i - k, 0), i))
print(dp[n-1])

### FIXED CODE ###

def main():
    n, k = [int(e) for e in input().split()]
    h = [int(e) for e in input().split()]
    dp = [0] * n
    for i in range(1, n):
        dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i - k, 0), i))
    print(dp[n-1])
main()
### BUGGY CODE ###

import numpy as np
N=int(input())

A=list(map(int,input().split()))
for i in range(N):
    A[i]=A[i]*2
C=[]
for i in range(N-1):
    B = [0] * (N)
    B[i]=0.5
    B[i+1]=0.5
    C.append(B)
B = [0] * (N)
B[0]=0.5
B[N-1]=0.5
C.append(B)

X=np.linalg.solve(C,A)
for i in range(N):
    print(int(X[i]/2),end=" ")




### FIXED CODE ###

N=int(input())
total=0
A=list(map(int,input().split()))
for i in range(N):
    total+=A[i]
for i in range(N):
    if i%2==1:
        total-=A[i]*2
print(int(total),end=" ")
for i in range(N-1):
    print(int(A[i]*2-total),end=" ")
    total=A[i]*2-total
### BUGGY CODE ###

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
    
dp = [[0]*(wmax+1) for _ in range(n+1)]

for i in range(1, n+1):
    for wi in range(1, wmax+1):
        if wi-w[i] >= 0:
            dp[i][wi] = max(dp[i-1][wi], dp[i-1][wi-w[i]]+v[i])
        else:
            dp[i][wi] = dp[i-1][wi]
            
print(dp[n][wmax])

### FIXED CODE ###

import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
    
dp = [[0]*(wmax+1) for _ in range(n+1)]

for i, wi in itr.product(range(1, n+1), range(1, wmax+1)):
    if wi-w[i] >= 0:
        dp[i][wi] = max(dp[i-1][wi], dp[i-1][wi-w[i]]+v[i])
    else:
        dp[i][wi] = dp[i-1][wi]
            
print(dp[n][wmax])
### BUGGY CODE ###

n = int(input())
s = input()
s = s.replace('R','0')
s = s.replace('G','1')
s = s.replace('B','2')
s = tuple(map(int,s))
rgb = [[0 for _ in range(3)] for _ in range(n+1)]
for i in range(n):
    for j in range(3):
        rgb[i+1][j] = rgb[i][j]
    rgb[i+1][s[i]] = rgb[i][s[i]] +1

ans = 0
for i in range(n):
    a = s[i]
    for j in range(i+1,n):
        b = s[j]
        if a != b:
            c = 3 -a- b
            ans += rgb[n][c] - rgb[j+1][c]
            if 2*j-i < n and s[2*j-i] == c:
                ans -= 1

print(ans)


### FIXED CODE ###

import collections
n = int(input())
a = input()
a = a.replace('R','1')
a = a.replace('G','2')
a = a.replace('B','3')
a = tuple(map(int,list(a)))
b = collections.Counter(a)
ans =b[3]*b[1]*b[2]
for i in range(n-2):
    for j in range(i+1,n):
        if a[i] == a[j]:
            continue
        c = j*2 -i
        if c < n:
            if a[i]+a[j]+a[c]==6:
                ans -= 1
        else:
            break
print(ans)
### BUGGY CODE ###

row = int(input())
item_list = [input() for i in range(row)]
result_list = []
for j in item_list:
  if j not in result_list:
    result_list.append(j)

print(len(result_list))


### FIXED CODE ###

row = int(input())
item_list = [input() for i in range(row)]
print(len(set(item_list)))
### BUGGY CODE ###

import numpy as np
height, width = map(int, input().split())
numofsquare = height*width
memoarray = np.zeros((height + 2, width + 2))
memoarray += numofsquare
existornot = 1
kaisu = 0
for i in range(1, height+1):
    S = input()
    for j in range(1, width+1):
        if S[j-1] == "#":
            memoarray[i, j] = 0


while existornot > 0:
    kaisu += 1
    existornot = 0
    for h in range(1, height + 1):
        for w in range(1, width + 1):
            if (memoarray[h, w] > kaisu):
                if memoarray[h - 1, w] == kaisu - 1 or memoarray[h, w - 1] == kaisu - 1 or memoarray[h, w + 1] == kaisu - 1 or memoarray[h + 1, w] == kaisu - 1:
                    memoarray[h, w] = kaisu
                    existornot += 1

print("{}".format(kaisu-1))


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while len(check_que) != 0:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)
### BUGGY CODE ###

n = int(input())
A = input().split()

s = 1
for i in range(n):
	s = s*int(A[i])
	
if s > 10**18:
	print(-1)
else:
	print(s)

### FIXED CODE ###

n = int(input())
A = input().split()
A.sort()

s = 1
for i in range(n):
	s*= int(A[i])
	if s > 10**18:
		print(-1)
		exit()

print(s)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc = [list(map(int,input().split())) for _ in range(q)]
N=[0]*(10**5+1)
for i in a:
    N[i]+=1
for b,c in bc:
    N[c] += N[b]
    N[b] = 0
    print(sum([i*x for i,x in enumerate(N) if x != 0]))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc = [list(map(int,input().split())) for _ in range(q)]
N=[0]*(10**5+1)
for i in a:
    N[i]+=1
ans = 0
for i,x in enumerate(N):
    if x != 0:
        ans += i*x #初期値

for b,c in bc:
    ans += (c-b)*N[b]
    N[c] += N[b]
    N[b] = 0
    print(ans)
### BUGGY CODE ###

n = int(input())
v = [int(c) for c in input().split()]
vo = v[::2]
ve = v[1::2]
counts_o = [(elm, vo.count(elm)) for elm in set(vo)]
counts_e = [(elm, ve.count(elm)) for elm in set(ve)]
counts_o.append((-1, 0))
counts_e.append((-2, 0))
counts_o.sort(key=lambda x:x[1])
counts_e.sort(key=lambda x:x[1])
if counts_o[-1][0] != counts_e[-1][0]:
	print(n - counts_o[-1][1] - counts_e[-1][1])
else:
	res1 = n - counts_o[-1][1] - counts_e[-2][1]
	res2 = n - counts_o[-2][1] - counts_e[-1][1]
	print(min(res1, res2))

### FIXED CODE ###

from collections import Counter

n = int(input())
v = [int(c) for c in input().split()]
vo = v[::2]
ve = v[1::2]
co = Counter(vo).most_common()
ce = Counter(ve).most_common()
co.append((-1, 0))
ce.append((-2, 0))
if co[0][0] != ce[0][0]:
	print(n - co[0][1] - ce[0][1])
else:
	res1 = n - co[0][1] - ce[1][1]
	res2 = n - co[1][1] - ce[0][1]
	print(min(res1, res2))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
AA=[0]*N
for i in range(N):
    AA[i]=A[i]%(10**9+7)

B=[0]*N
c=0

for i in range(N-1):
    for j in range(i+1,N):
      B[j]=(A[i]*AA[j])%(10**9+7)
      c=(c+B[j])%(10**9+7)
print(c)

### FIXED CODE ###

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

c=0
for i in range(N):
    c=c+A[i]**2
    
print((sum(A)**2-c)//2%(10**9+7))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def binbin(binn):
    return bin(binn).count("1")

def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))

def main():
    N = int(input())
    X = input().strip()

    x = 0
    for i in range(N):
        if X[-1 - i] == '1':
            x += pow(2, i)
    xc = binbin(x)
    x1 = x % (xc + 1)
    if xc == 1:
        x2 = -1
    else:
        x2 = x % (xc - 1)
    for i in range(N):
        z = pow(2, N - i - 1)
        if X[i] == '0':
            if x + z == 0:
                print(0)
            else:
                print(1 + popcount((x1 + z % (xc + 1)) % (xc + 1)))
        else:
            if x - z == 0:
                print(0)
            else:
                if x2 == -1:
                    print(0)
                else:
                    print(1 + popcount((x2 - z % (xc - 1)) % (xc - 1)))



    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def binbin(binn):
    return bin(binn).count("1")


def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))


def main():
    N = int(input())
    X = input().strip()

    x1 = 0
    xc = binbin(int(X, 2))
    if xc == 1:
        x2 = -1
    else:
        x2 = 0
    for i in range(N):
        if X[-1 - i] == '1':
            x1 += pow(2, i, xc + 1)
            if x2 != -1:
                x2 += pow(2, i, xc - 1)
    for i in range(N):
        if X[i] == '0':
            print(1 + popcount((x1 + pow(2, N - i - 1, xc + 1)) % (xc + 1)))
        else:
            if x2 == -1:
                print(0)
            else:
                print(1 + popcount((x2 - pow(2, N - i - 1, xc - 1) + xc - 1) % (xc - 1)))


if __name__ == '__main__':
    main()