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

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

for ai in a:
  if not a_pop.get(ai):
    a_pop[ai] = 1
  else:
    a_pop[ai] += 1

for ai in a:
  ans = 0
  for k, v in a_pop.items():
    if k == ai:
      if v > 2:
        ans += (v - 1) * (v - 2) // 2
    else:
      if v > 1:
        ans += v * (v - 1) // 2
  print(ans)

### FIXED CODE ###

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

for ai in a:
  if not a_pop.get(ai):
    a_pop[ai] = 1
  else:
    a_pop[ai] += 1

hoge = sum(v * (v - 1) // 2 for v in a_pop.values())

for ai in a:
  ans = hoge
  v = a_pop[ai]
  print(ans - (v - 1))
### BUGGY CODE ###

def main() :
    N, M  = list(map(int, input().split()))
    H     = list(map(int, input().split()))
    LEFT  = 0
    RIGHT = 1
    pairs = []

    for itr in range(M) :
        pairs.append(list(map(int, input().split())))

    
    resurt = 0
    for itr in range(N) :
        checkl = []
        for inner_itr in range(N) :
            checkl.append(False)
        
        count = 1
        for inner_itr in range(M) :
            if pairs[inner_itr][LEFT] == (itr + 1) :
                if H[itr] <= H[pairs[inner_itr][RIGHT] - 1] :
                    count = 0
                    break
                checkl[RIGHT - 1] = True                    

            if pairs[inner_itr][RIGHT] == (itr + 1) :
                if H[itr] <= H[pairs[inner_itr][LEFT] - 1] :
                    count = 0
                    break
                checkl[LEFT - 1] = True
        resurt += count
        checkl = None
    
    print(resurt)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
import copy

def main():
    N, M  = list(map(int, input().split()))
    H     = list(map(int, input().split()))
    maxH  = np.zeros(N)

    for itr in range(M):
        A, B = list(map(int, input().split()))
        if H[A- 1] == H[B- 1] :
            maxH[A- 1] = copy.copy(H[A- 1]) + 1
            maxH[B- 1] = copy.copy(H[A- 1]) + 1
        elif H[A- 1] > H[B- 1] :
            if maxH[A- 1] < H[A- 1] :
                maxH[A- 1] = copy.copy(H[A- 1])
            if maxH[B- 1] < H[A- 1] :
                maxH[B- 1] = copy.copy(H[A- 1])
        elif H[A- 1] < H[B- 1] :
            if maxH[A- 1] < H[B- 1] :
                maxH[A- 1] = copy.copy(H[B- 1])
            if maxH[B- 1] < H[B- 1] :
                maxH[B- 1] = copy.copy(H[B- 1])
    
    result = 0
    for itr in range(N):
        if H[itr] == maxH[itr] or maxH[itr] == 0:
            result += 1
    #print(maxH)
    print(result)

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

import sys
H, W, N = map(int,input().split())
if N ==0:
  print((H-2)*(W-2))
  for i in range(9): print(0)
  sys.exit()
  
blacks = [[0 for i in range(W+2)] for j in range(H+2)]
for i in range(N):
  a, b = map(int,input().split())
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      blacks[a+dx][b+dy]+=1

ans =[0 for i in range(10)]
for j in range(2,H):
  for i in range(2,W):
    ans[blacks[j][i]]+=1
for i in range(10): print(ans[i])

### FIXED CODE ###

import sys
from collections import defaultdict

H, W, N = map(int,input().split())
if N ==0:
  print((H-2)*(W-2))
  for i in range(9): print(0)
  sys.exit()
  
ans =[(H-2)*(W-2)]+[0]*9
blacks = defaultdict(int)
for i in range(N):
  a, b = map(int,input().split())
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      if 2 <= a+dx <H and 2 <= b+dy <W:
        ans[blacks[(a+dx,b+dy)]]-=1
        ans[blacks[(a+dx,b+dy)]+1]+=1
      blacks[(a+dx,b+dy)]+=1
        
for i in range(10): print(ans[i])
### BUGGY CODE ###

import functools
import operator
n = int(input())
a = list(map(int, input().split()))
 
ans = functools.reduce(operator.mul, a)
if ans > 10 ** 18:
    print('-1')
else:
    print(ans)

### FIXED CODE ###

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

if 0 in a:
    ans = 0
else:
    ans = 1
    for i in range(n):
        ans = ans * a[i]
        if ans > 10 ** 18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

import sys
import math
import bisect

def solve(n):
    ans = 0
    for i in range(n + 1):
        if i ** 2 <= n:
            ans = i ** 2
    return ans

def main():
    n = int(input())
    print(solve(n))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math
import bisect

def solve(n):
    return math.floor(math.sqrt(n)) ** 2

def main():
    n = int(input())
    print(solve(n))

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

# -*- coding: utf-8 -*-
# get a integer
num = int(raw_input())
# get two integers separated with half-width break
array = map(int, raw_input().split())
# get a string
#s = raw_input()

for i in range(0,num):
    state = 0
    way = 0
    for j in range(0,num):
        if i != j:
            way += abs(array[j] - state)
            state = array[j]
    way += abs(state)
    print(way)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# get a integer
num = int(raw_input())
# get two integers separated with half-width break
array = map(int, raw_input().split())
# get a string
#s = raw_input()

state = 0
way_total = 0
for j in range(0,num):
    way_total += abs(array[j] - state)
    state = array[j]
way_total += abs(state)

for i in range(0,num):
    if i != num - 1 and i != 0:
        way = way_total - abs(array[i-1] - array[i]) - abs(array[i+1] - array[i]) + abs(array[i-1] - array[i+1])
    elif i == 0:
        way = way_total - abs(array[i])- abs(array[i+1] - array[i]) + abs(array[i+1])
    elif i == num - 1:
        way = way_total - abs(array[i-1] - array[i]) - abs(array[i]) + abs(array[i-1] - 0)
    print(way)
### BUGGY CODE ###

N=int(input())
count = 0
for a in range(1,1000001):
	for b in range(1,1000001):
		if a*b<N:
			count+=1
		else:
			break
print(count)

### FIXED CODE ###

N=int(input())
count = 0
for a in range(1,1000001):
	count+=(N-1)//a
print(count)
### BUGGY CODE ###

N=int(input())
temp=input().split()
d=[int(temp[i]) for i in range(N)]
dd=[]
for i in range(int(N/2)+1):
  dd.append(min(d))
  d.remove(min(d))
  
a=dd[int(N/2-1)]
b=dd[int(N/2)]
print(int(b-a))

### FIXED CODE ###

N=int(input())
temp=input().split()
d=[int(temp[i]) for i in range(N)]
d.sort()
  
a=d[int(N/2-1)]
b=d[int(N/2)]
print(int(b-a))
### BUGGY CODE ###

S = input()
Q = int(input())
 
alpha_map = {chr(i):i for i in range(97,123)}
alpha_map_inv = {i:chr(i) for i in range(97,123)}
a = [0] * len(S)
for i, s in enumerate(S):
  a[i] = alpha_map[s]

reversed = False

for _ in range(Q):
  query = list(map(str, input().split()))
  if query[0] == '1':
    if reversed:
      reversed = False
    else:
      reversed = True
  else:
    if (query[1] == '1')&(not reversed):
      a.insert(0,alpha_map[query[2]])
    elif (query[1] == '2')&(reversed):
      a.insert(0,alpha_map[query[2]])
    else:
      a.append(alpha_map[query[2]])
ss = [''] * len(a)
for i, aa in enumerate(a):
  ss[i] = alpha_map_inv[aa]
if reversed:
  ss.reverse()
print(''.join(ss))

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
 
alpha_map = {chr(i):i for i in range(97,123)}
alpha_map_inv = {i:chr(i) for i in range(97,123)}
a = deque()
for s in S:
  a.append(s)
reversed = False
 
for _ in range(Q):
  query = list(map(str, input().split()))
  if query[0] == '1':
    if reversed:
      reversed = False
    else:
      reversed = True
  else:
    if (query[1] == '1')&(not reversed):
      a.appendleft(query[2])
    elif (query[1] == '2')&(reversed):
      a.appendleft(query[2])
    else:
      a.append(query[2])
if reversed:
  a.reverse()
print(''.join(list(a)))
### BUGGY CODE ###

n = int(input())
 
arr6 = []
for i in range(10):
    arr6.append(6**i)

arr9 = []
for i in range(10):
    arr9.append(9**i)

ans = float("inf")
for i in range(n+1):
    count = 0
    tmp = i
    while tmp > 0:
        t = 0
        while arr6[t] <= tmp:
            t+=1

        tmp -= arr6[t-1]
        count += 1

    tmp = n-i
    while tmp > 0:
        t = 0
        while arr9[t] <= tmp:
            t += 1
        tmp -= arr9[t-1]
        count += 1

    ans = min(ans,count)

print(ans)


### FIXED CODE ###

N = int(input())

dp = [float("inf") for _ in range(100010)]
dp[0] = 0

for i in range(1, N+1):
    power = 1
    while power <= i:
        dp[i] = min(dp[i], dp[i-power]+1)
        power *= 6
    
    power = 1
    while power <= i:
        dp[i] = min(dp[i], dp[i-power]+1)
        power *= 9
print(dp[N])
### BUGGY CODE ###

from operator import mul
from functools import reduce

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

sum_num = reduce(mul, input_list)

if sum_num > 10 ** 18:
    print('-1')
else:
    print(sum_num)

### FIXED CODE ###

N = int(input())
input_list = [int(i) for i in input().split()]
max_num = 10 ** 18

sum_num = 1
if 0 in input_list:
    print('0')
else:
    for i in input_list:
        sum_num *= i
        if sum_num > max_num:
            sum_num = -1
            break
    print(sum_num)
### BUGGY CODE ###

import array
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx]==0 : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i]==0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i]==0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
 
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.999
ANS = array.array('I',[0]*N)
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n, k = map(int, raw_input().split())
baggages = []
weight_sum = 0
for i in range(n):
    baggages.append(int(raw_input()))
for i in baggages:
    weight_sum += i
P_min = int(weight_sum/k)
tmp = P_min
while True:
    flag = True
    trucks = k-1
    i = 0
    while i < n:
        baggage = baggages[i]
        if P_min < baggage:
            P_min = baggage-1
            flag = False
            break
        if tmp >= baggage:
            tmp -= baggage
            i += 1
        else:
            tmp = P_min
            if trucks > 0:
                trucks -= 1
            else:
                flag = False
                break
    if flag:
        break
    else:
        P_min += 1
        tmp = P_min
print P_min

### FIXED CODE ###

# -*- coding: utf-8 -*-

def maxStack(k, p, W):
    nw = 0
    count = 0
    t = 1
    for x in W:
        if x > p:
            return count
        if nw + x <= p:
            nw += x
            count += 1
        else:
            if t == k:
                return count
            else:
                t += 1
                nw = x
                count += 1
    return count

n, k = map(int, raw_input().split())
W = [int(raw_input()) for i in range(n)]
left = 1
right = sum(W)
while left < right:
    mid = (left+right)/2
    v = maxStack(k, mid, W)
    if v >= n:
        right = mid
    else:
        left = mid+1
print left
### BUGGY CODE ###

def Replacing():

    Num = int(input())

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

    NumB = int(input())

    for i in range(NumB):
        value_B = list(map(int,input().split()))

        value_A = [value_B[1] if j == value_B[0] else j for j in value_A]

        print(sum(value_A))

if __name__ == '__main__':
    Replacing()


### FIXED CODE ###

from collections import Counter

def Replacing():

    Num = int(input())

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

    Sum = sum(value_A)
    Counter_value = Counter(value_A)

    NumB = int(input())

    for i in range(NumB):
        value_B = list(map(int,input().split()))

        Sum += (value_B[1] - value_B[0])*Counter_value[value_B[0]]
        Counter_value[value_B[1]] += Counter_value[value_B[0]]
        Counter_value[value_B[0]] = 0

        print(Sum)

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

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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

sum_val = 0
for i in range(n-k+1):
    val = cmb(n-i-1, k-1)
    sum_val = (sum_val + a_list[-(i+1)]*val - a_list[i]*val)%(10**9+7)

print(sum_val)

### FIXED CODE ###

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


mod = 10 ** 9 + 7
f_list = [1]
for i in range(1,n+1):
    f_list.append((f_list[-1] * i) % mod)
def comb(n,r):
    return f_list[n] * (pow(f_list[r], mod-2, mod) * pow(f_list[n-r], mod-2, mod) % mod) % mod


max_val = 0
min_val = 0
for i in range(n - k + 1):
    val = comb(n - i - 1, k - 1)
    max_val = (max_val + (((a_list[-(i + 1)]) * val))) % (10 ** 9 + 7)
    min_val = (min_val + ((a_list[i]) * val)) % (10 ** 9 + 7)

print(int((max_val - min_val) % (10 ** 9 + 7)))
### BUGGY CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))
A=[0]*n
for i in range(1,n):
  A[i]=min(A[i-j]+abs(H[i]-H[i-j]) for j in range(1,min(i+1,k+1)))
print(A[n-1])

### FIXED CODE ###

def solve():
  n,k=map(int,input().split())
  H=list(map(int,input().split()))
  A=[0]*n
  for i in range(1,n):
    A[i]=min(A[i-j]+abs(H[i]-H[i-j]) for j in range(1,min(i+1,k+1)))
  return A[n-1]
print(solve())
### BUGGY CODE ###

n = int(input())

ans = 0
for i in range(1,n+1):
  #項数
  kousu=n//i
  #一般項
  an = i + (kousu-1)*i
  #和の公式
  sn = (i + an)*kousu//2
  ans += sn
print(ans)


### FIXED CODE ###

n = int(input())

ans = 0
for i in range(1,n+1):
  #項数
  kousu=n//i
  #一般項
  an = i + (kousu-1)*i
  #和の公式
  sn = (i + an)*kousu//2
  ans += sn
print(ans)
### BUGGY CODE ###

n,k=[int(j)for j in input().split()]
a=[int(j)for j in input().split()]
if n<=k:
    print(*[n]*n)
    exit()
import copy
for _ in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
print(*a)








### FIXED CODE ###

n,k=[int(j)for j in input().split()]
a=[int(j)for j in input().split()]
if n<=k:
    print(*[n]*n)
    exit()
import copy
for _ in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
    if a==[n]*n:
        break
print(*a)
### BUGGY CODE ###

def main():
    n, ma, mb = map(int, input().split())
    ABC = []
    for i in range(n):
        a, b, c = map(int, input().split())
        ABC.append((a, b, c))

    INF = 10**18
    dp = [[[INF]*405 for i in range(405)] for j in range(n+1)]
    dp[0][0][0] = 0
    for i in range(n):
        a, b, c = ABC[i]
        for j in range(405):
            for k in range(405):
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                nj, nk = j+a, k+b
                if 1 <= nj <= 404 and 1 <= nk <= 404:
                    dp[i+1][nj][nk] = min(dp[i][nj][nk], dp[i][j][k]+c)

    import fractions
    ans = INF
    for j in range(1, 405):
        for k in range(1, 405):
            if ma*k == mb*j:
                ans = min(ans, dp[n][j][k])
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, ma, mb = map(int, input().split())
    ABC = []
    for i in range(n):
        a, b, c = map(int, input().split())
        ABC.append((a, b, c))

    INF = 10**18
    dp = [[[INF]*405 for i in range(405)] for j in range(n+1)]
    dp[0][0][0] = 0
    for i in range(n):
        a, b, c = ABC[i]
        for j in range(405):
            for k in range(405):
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                nj, nk = j+a, k+b
                if 1 <= nj <= 404 and 1 <= nk <= 404:
                    dp[i+1][nj][nk] = min(dp[i][nj][nk], dp[i][j][k]+c)

    import fractions
    ans = INF
    for j in range(1, 405):
        for k in range(1, 405):
            if ma*k == mb*j:
                ans = min(ans, dp[n][j][k])
    if ans == INF:
        print(-1)
    else:
        print(ans)

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

import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())

VACANT = 'Vacant'
FEMALE = 'Female'
MALE = 'Male'


def check(n):
    print(n, flush=True)
    s = sys.stdin.buffer.readline().decode().rstrip()
    if s == VACANT:
        exit()
    return s


l = 0
h = N - 1
ls = check(l)
while abs(l - h) > 1:
    mid = (l + h) // 2
    ms = check(mid)
    if ((mid - l) % 2 == 0) == (ls == ms):
        l = mid
    else:
        h = mid
check(l)
check(h)


### FIXED CODE ###

import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())

VACANT = 'Vacant'
FEMALE = 'Female'
MALE = 'Male'


def check(n):
    print(n, flush=True)
    s = sys.stdin.buffer.readline().decode().rstrip()
    if s == VACANT:
        exit()
    return s


l = 0
h = N
ls = check(l)
while abs(l - h) > 1:
    mid = (l + h) // 2
    ms = check(mid)
    if ((mid - l) % 2 == 0) == (ls == ms):
        l = mid
        ls = ms
    else:
        h = mid
check(h)
check(l)
### BUGGY CODE ###

def main():
    a,b,c=map(int,input().split())
    d=[]
    for i in range(c+1):
        e=(a*i)//b-a*(i//b)
        d.append(e)
    print(max(d))
if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
a,b,c=map(int,input().split())
if b>c:
    print(math.floor((a*c)/b)-a*(math.floor(c/b)))
else:
    print(math.floor((a*(b-1))/b)-a*(math.floor((b-1)/b)))
### BUGGY CODE ###

n, w = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    for j in range(1, wi):
        dp[i % 2][j] = dp[1 - i % 2][j]
    for j in range(wi, w + 1):
        dp[i % 2][j] = max(dp[1 - i % 2][j], dp[1 - i % 2][j - wi] + vi)
print(max(dp[i % 2]))


### FIXED CODE ###

n, w = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))
### BUGGY CODE ###


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

S = sorted(A)

for i in range(N):
    if A[i] == max(S):
        print(S[-2])
    else:
        print(S[-1])



### FIXED CODE ###

# N = int(input())
# A = list(map(int, input().split()))
# 
# S = sorted(A)
# MAXS = max(A)
# 
# for i in range(N):
#     if A[i] == MAXS:
#         print(S[-2])
#     else:
#         print(S[-1])
# 


n = int(input())
a = list()
for i in range(n):
    a.append(int(input()))
c = a.index(max(a))
m = max(a)
a.sort()
d = a[-2]
for i in range(n):
    if i == c:
        print(d)
    else:
        print(m)
### BUGGY CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)



### FIXED CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)
### BUGGY CODE ###

from itertools import accumulate

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

L={}
for i in range(n+1):
      if b[i] in b:
            if b[i] in L:
                  L[b[i]]+=1
            else:
                  L[b[i]]=1
ans=0
for i in L.values():
      if i>1:
            ans+=i*(i-1)//2
print(ans)     


### FIXED CODE ###

import collections

n=int(input())
*a,=map(int,input().split())
 
b=[0]
 
for i in range(n):
  b.append(a[i]+b[i])
 
L=collections.Counter(b)

ans=0
for i in L.values():
      if i>1:
            ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))

for i in range(m):
    A[-1] /= 2
    A.sort()

A = map(int, A)

print(sum(A))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
A = sorted(list(map(lambda x: int(x)*(-1), input().split())))

heapq.heapify(A)

for i in range(m):
    a = heapq.heappop(A)
    a = a * (-1) // 2
    heapq.heappush(A, -a)

print(-sum(A))