Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    a, b, n = map(int, input().split())
    ans = -10 ** 10

    if b - 1 <= n:
        x = b - 1
        ans = (a * x) // b - a * (x // b)
    else:
        for x in range(1, n + 1):
            ans = max(ans, (a * x) // b - a * (x // b))

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def f(a, b, x):
    return (a * x) // b - a * (x // b)


def main():
    a, b, n = map(int, input().split())

    if n < b - 1:
        x = n
    else:
        x = b - 1

    print(f(a, b, x))


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = input()
    r_list, g_list, b_list = [], [], []

    for i, c in enumerate(s):
        if c == "R":
            r_list.append(i)
        elif c == "G":
            g_list.append(i)
        elif c == "B":
            b_list.append(i)

    cnt = 0
    for r in r_list:
        for g in g_list:
            for b in b_list:
                if r < g < b and g - r != b - g:
                    cnt += 1
                elif r < b < g and b - r != g - b:
                    cnt += 1
                elif g < r < b and r - g != b - r:
                    cnt += 1
                elif g < b < r and b - g != r - b:
                    cnt += 1
                elif b < r < g and r - b != g - r:
                    cnt += 1
                elif b < g < r and g - b != r - g:
                    cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    n = int(input())
    s = input()
    r_set, g_set, b_set = set(), set(), set()

    for i, c in enumerate(s):
        if c == "R":
            r_set.add(i)
        elif c == "G":
            g_set.add(i)
        elif c == "B":
            b_set.add(i)

    cnt = 0
    for i in range(n):
        for j in range(i + 1, n):
            k = 2 * j - i

            if i in r_set and j in g_set and k in b_set:
                cnt += 1
            elif i in r_set and j in b_set and k in g_set:
                cnt += 1
            elif i in g_set and j in r_set and k in b_set:
                cnt += 1
            elif i in g_set and j in b_set and k in r_set:
                cnt += 1
            elif i in b_set and j in r_set and k in g_set:
                cnt += 1
            elif i in b_set and j in g_set and k in r_set:
                cnt += 1

    print(len(r_set) * len(g_set) * len(b_set) - cnt)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    a_list = list(map(int, input().split()))

    a_dict = {}
    for a in a_list:
        if a not in a_dict:
            a_dict[a] = 1
        else:
            a_dict[a] += 1

    for k in range(n):
        cnt = 0
        a_dict[a_list[k]] -= 1
        for v in a_dict.values():
            if v >= 2:
                cnt += v * (v - 1) // 2
        a_dict[a_list[k]] += 1
        print(cnt)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    num_list = [0] * n  # 各番号が書かれたボールが何個あるか
    method_list = [0] * n  # 同じ番号が書かれた異なる2つのボールを選ぶ方法

    for a in a_list:
        num_list[a - 1] += 1

    for i in range(n):
        b = num_list[i]
        if b >= 2:
            method_list[i] = b * (b - 1) // 2

    total_method = sum(method_list)

    for k in range(n):
        c = a_list[k]  # k番目のボールに書かれている数字
        ans = total_method - method_list[c - 1]
        d = num_list[c - 1]
        if d >= 3:
            e = (d - 1) * (d - 2) // 2
        else:
            e = 0
        ans += e
        print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    q = int(input())

    for _ in range(q):
        query = list(input())
        if query[0] == "1":
            s = s[::-1]
        elif query[0] == "2":
            if query[2] == "1":
                s = query[4] + s
            elif query[2] == "2":
                s = s + query[4]

    print(s)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    s = input()
    q = int(input())
    d = deque(s)
    is_reversed = False

    for _ in range(q):
        query = list(input().split())

        if query[0] == "1":
            if is_reversed:
                is_reversed = False
            else:
                is_reversed = True

        elif query[0] == "2":
            if query[1] == "1":
                if is_reversed:
                    d.append(query[2])
                else:
                    d.appendleft(query[2])
            elif query[1] == "2":
                if is_reversed:
                    d.appendleft(query[2])
                else:
                    d.append(query[2])

    if is_reversed:
        print(*(list(d)[::-1]), sep="")
    else:
        print(*list(d), sep="")


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    p_lst = list(map(int, input().split()))

    ans = 0

    for i in range(n):
        if min(p_lst[:i + 1]) >= p_lst[i]:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    n = int(input())
    p_lst = list(map(int, input().split()))

    min_val = n + 1
    ans = 0

    for i in range(n):
        if min_val > p_lst[i]:
            min_val = p_lst[i]
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    A = input()
    B = input()

    if A == "1" and B == "2":
        ans = 3
    elif A == "2" and B == "3":
        ans = 1
    elif A == "3" and B == "1":
        ans = 2

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    A = int(input())
    B = int(input())

    ans = 6 - A - B

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    S = input()

    password = set()

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            for k in range(10):
                if str(k) in S[j + 1:]:
                    password.add(S[i] + S[j] + str(k))

    print(len(password))


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N = int(input())
    S = input()
    ans = 0
    # password = set()

    # for i in range(N - 2):
    #     for j in range(i + 1, N - 1):
    #         for k in range(10):
    #             if str(k) in S[j + 1:]:
    #                 password.add(S[i] + S[j] + str(k))

    for i in range(10):
        for j in range(10):
            for k in range(10):
                i_index = S.find(str(i))
                j_index = S.find(str(j), i_index + 1)
                k_index = S.find(str(k), j_index + 1)
                if i_index != -1 and j_index != -1 and k_index != -1:
                    ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    S = input()

    password = set()

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            for k in range(j + 1, N):
                candidate = S[i] + S[j] + S[k]
                password.add(candidate)

    print(len(password))


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N = int(input())
    S = input()
    ans = 0
    # password = set()

    # for i in range(N - 2):
    #     for j in range(i + 1, N - 1):
    #         for k in range(10):
    #             if str(k) in S[j + 1:]:
    #                 password.add(S[i] + S[j] + str(k))

    for i in range(10):
        for j in range(10):
            for k in range(10):
                i_index = S.find(str(i))
                j_index = S.find(str(j), i_index + 1)
                k_index = S.find(str(k), j_index + 1)
                if i_index != -1 and j_index != -1 and k_index != -1:
                    ans += 1

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, X = map(int, input().split())
    L = list(map(int, input().split()))
    cnt = 1
    D = 0

    while True:
        if D > X:
            cnt -= 1
            break
        if cnt > N + 1:
            cnt -= 1
            break
        D += L[cnt - 1]
        cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N, X = map(int, input().split())
    L = list(map(int, input().split()))
    D = 0

    for cnt in range(2, N + 2):
        D += L[cnt - 2]
        if D > X:
            cnt -= 1
            break

    print(cnt)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, m = map(int, input().split())
    lr_lst = [list(map(int, input().split())) for _ in range(m)]

    ans = 0

    for i in range(1, n + 1):
        is_able = True
        for j in range(m):
            if not lr_lst[j][0] <= i <= lr_lst[j][1]:
                is_able = False
                break
        if is_able:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    n, m = map(int, input().split())
    lr_lst = [list(map(int, input().split())) for _ in range(m)]
    left = 0
    right = n + 1

    for i in range(m):
        if left < lr_lst[i][0]:
            left = lr_lst[i][0]
        if lr_lst[i][1] < right:
            right = lr_lst[i][1]

    if right - left < 0:
        print(0)
    else:
        print(right - left + 1)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    S = input()
    ans = N

    for i in range(N):
        cnt = S[:i].count("W") + S[i + 1:].count("E")
        if cnt < ans:
            ans = cnt

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N = int(input())
    S = input()
    lst = [0] * N
    ans = N

    if S[0] == "E":
        lst[0] = 1
    for i in range(1, N):
        if S[i] == "E":
            lst[i] = lst[i - 1] + 1
        else:
            lst[i] = lst[i - 1]

    for i in range(N):
        if i == 0:
            left = 0
        else:
            left = i - lst[i - 1]
        right = lst[N - 1] - lst[i]

        if left + right < ans:
            ans = left + right

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
	N = int(input())
	a = list(map(int, input().split()))

	ans = [0] * (10 ** 5 + 1)

	for X in range(10 ** 5 + 1):
		if X == 0:
			ans[0] += a.count(0)
			ans[0] += a.count(1)
		elif X == 10 ** 5:
			ans[10 ** 5] += a.count(10 ** 5 - 1)
			ans[10 ** 5] += a.count(10 ** 5 + 1)
		else:
			ans[X] += a.count(X - 1)
			ans[X] += a.count(X)
			ans[X] += a.count(X + 1)

	print(max(ans))

 
if __name__ == "__main__":
  	main()

Fixed submission:
def main():
	N = int(input())
	a = list(map(int, input().split()))
	
	a_lst = [0] * (10 ** 5 + 1)
	for num in a:
		a_lst[num] += 1

	ans = 0
	for X in range(10 ** 5 + 1):
		cnt = 0

		if X == 0:
			cnt += a_lst[X]
			cnt += a_lst[X + 1]
		elif X == 10 ** 5:
			cnt += a_lst[X - 1]
			cnt += a_lst[X]
		else:
			cnt += a_lst[X - 1]
			cnt += a_lst[X]
			cnt += a_lst[X + 1]

		if cnt > ans:
			ans = cnt

	print(ans)



 
if __name__ == "__main__":
  	main()
Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    rate_list = [0] * 9

    for a in a_list:
        rate_list[a // 400] += 1

    min_cnt = 0
    for i in range(8):
        if rate_list[i] > 0:
            min_cnt += 1

    print(min_cnt, min_cnt + rate_list[-1])


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    rate_list = [0] * 9

    for a in a_list:
        rate = a // 400
        if rate < 8:
            rate_list[rate] += 1
        else:
            rate_list[-1] += 1

    min_cnt = 0
    for i in range(8):
        if rate_list[i] > 0:
            min_cnt += 1

    print(max(min_cnt, 1), min_cnt + rate_list[-1])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
a=[]

for i in range(6):
    a.append(int(input())

a=sort(a)
if(a[4]-a[0]>a[5]):
    print(':(')
else:
    print('Yay!')

Fixed submission:
a=[]

for i in range(5):
    a.append(int(input()))

k=int(input())
for i in range(5):
    for j in range(5):
        if(i==j):
            continue
        else:
            if(abs(a[i]-a[j])>k):
                print(':(')
                exit()

print('Yay!')

Buggy python submission (verdict: Runtime Error):
a=[]

for i in range(6):
    a.append(int(input())

a=a.sort()
if(a[4]-a[0]>a[5]):
    print(':(')
else:
    print('Yay!')

Fixed submission:
a=[]

for i in range(5):
    a.append(int(input()))

k=int(input())
for i in range(5):
    for j in range(5):
        if(i==j):
            continue
        else:
            if(abs(a[i]-a[j])>k):
                print(':(')
                exit()

print('Yay!')

Buggy python submission (verdict: Runtime Error):
a=[]

for i in range(6):
  a.append(int(input())

a=a.sort()
if(a[4]-a[0]>a[5]):
    print(':(')
else:
    print('Yay!')

Fixed submission:
a=[]

for i in range(5):
    a.append(int(input()))

k=int(input())
for i in range(5):
    for j in range(5):
        if(i==j):
            continue
        else:
            if(abs(a[i]-a[j])>k):
                print(':(')
                exit()

print('Yay!')
Buggy python submission (verdict: Runtime Error):
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <map>
#include <string>
#include <utility>

#define repd(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue(){
	int a;
	cin >> a;
	return a;
}

void inputArray(int *p,int a){
	rep(i,a){
		cin >> p[i];
	}
}

void inputVector(vector<int> *p,int a){
	rep(i,a){
		int input;
		cin >> input;
		p -> push_back(input);
	}
}

template <typename T>
void output(T a,int precision){
	if(precision > 0){
		cout << setprecision(precision) << a << "\n";
	}else{
		cout << a << "\n";
	}
}

vector<ll> a,p;
ll f(ll n,ll x){
	if(n==0){
		if(x<=0){
			return 0;
		}else{
			return 1;
		}
	}else if(x<=1+a[n-1]){
		return f(n-1,x-1);
	}else{
		return p[n-1]+1+f(n-1,x-2-a[n-1]);
	}
}

int main(){
	//source
	ll n,x;
	cin >> n >> x;
	a.push_back(1);
	p.push_back(1);
	rep(i,n){
		a.push_back(a[i]*2+3);
		p.push_back(p[i]*2+1);
	}

	cout << f(n,x) << endl;
	return 0;
}


Fixed submission:
import numpy as np

n,x=map(int,input().split())
a,p=[1],[1]
for i in range(n):
	a.append(a[i]*2+3)
	p.append(p[i]*2+1)

def f(N,X):
	if N==0:
		return 0 if X<=0 else 1
	elif X <=1+a[N-1]:
		return f(N-1,X-1)
	else:
		return p[N-1]+1+f(N-1,X-2-a[N-1])
	
print (f(n,x))


def inputList():
	a=list(map(int,input().split()))
	return a

def multisort(li,index):
	return sorted(li,key=lambda x: x[index])
Buggy python submission (verdict: Runtime Error):
import numpy as np

def main():
    a=inputList()
    if(a[0]>a[1]):
        print("GREATER")
    elif(a[0]<a[1]):
        print("LESS")
    else:
        print("EQUAL")

def inputList():
    a=list(map(int,input().split()))
    return a

def multisort(li,index):
    return sorted(li,key=lambda x: x[index])

if(__name__=='__main__'):
    main()


Fixed submission:
import numpy as np

def main():
    a=int(input())
    b=int(input())
    if(a>b):
        print("GREATER")
    elif(a<b):
        print("LESS")
    else:
        print("EQUAL")

def inputList():
    a=list(map(int,input().split()))
    return a

def multisort(li,index):
    return sorted(li,key=lambda x: x[index])

if(__name__=='__main__'):
    main()
Buggy python submission (verdict: Runtime Error):
tmpn,k=map(int,input().split())
a=[int(input()) for _ in range(tmpn)]
n=3*10**5+2

def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

#####単位元######
ide_ele_max = 0

#num_max:n以上の最小の2のべき乗
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

init_max([0]*n)

for aa in a:
    aa+=1
    maxlen=query_max(aa-k,aa+k+1)
    update_max(aa,maxlen+1)

print(query_max(0,n+1))

Fixed submission:
tmpn,k=map(int,input().split())
a=[int(input()) for _ in range(tmpn)]
n=3*10**5+1

def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

#####単位元######
ide_ele_max = 0

#num_max:n以上の最小の2のべき乗
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

init_max([0]*n)

for aa in a:
    maxlen=query_max(max(0,aa-k),min(aa+k,n-1)+1)
    update_max(aa,maxlen+1)

print(query_max(0,n+1))
Buggy python submission (verdict: Runtime Error):
n=int(input())
*a,=map(int,open(0).read().split())



for i in range(2,2*n):
    if a[i-2]==a[i-1]==a[i]:
        print('Yes')
        break
else:
    print('No')

Fixed submission:
n=int(input())
d=[list(map(int,input().split())) for _ in range(n)]

cnt=0

for i in range(n):
    if d[i][0]==d[i][1]:
        cnt+=1
        if cnt>=3:
            print('Yes')
            exit(0)
    else:
        cnt=0

print('No')
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
*p,=map(int,input().split())
*c,=map(int,input().split())

ans=-10**20
for i in range(n):
    loop=1
    j=p[i]-1
    acm=[c[j]]
    while j!=i:
        j=p[j]-1
        acm.append(acm[-1]+c[j])
        loop+=1
    
    if acm[-1]>0:
        if k<loop:
            cur=max(acm[:k])
        else:
            cur=(k//loop)*acm[-1]
            cur=max(cur,cur+max(acm[:k%loop]))
    else:
        cur=max(acm[:min(k,loop)])
    
    ans=max(cur,ans)

print(ans)

Fixed submission:
n,k=map(int,input().split())
*p,=map(int,input().split())
*c,=map(int,input().split())

ans=-10**20
for i in range(n):
    loop=1
    j=p[i]-1
    acm=[c[j]]
    while j!=i:
        j=p[j]-1
        acm.append(acm[-1]+c[j])
        loop+=1
    
    if acm[-1]>0:
        if k<=loop:
            cur=max(acm[:k])
        else:
            cur=(k//loop)*acm[-1]
            if k%loop>0:
                cur=max(cur,cur+max(acm[:k%loop]))
            else:
                cur-=acm[-1]
                cur+=max(acm)
    else:
        cur=max(acm[:min(k,loop)])
    
    ans=max(cur,ans)
    
print(ans)
Buggy python submission (verdict: Runtime Error):
n,d=list(map(int,input().split()))

cnt=0

for x,y in list(map(int,input().split())):
    if x**2+y**2<=d**2:
        cnt+=1

print(cnt)

Fixed submission:
n,d=list(map(int,input().split()))

cnt=0

for _ in range(n):
    x,y=list(map(int,input().split()))
    if x**2+y**2<=d**2:
        cnt+=1

print(cnt)
Buggy python submission (verdict: Runtime Error):
n,k=list(map(int,input().split()))
alst=list(map(int,input().split()))

ok=max(alst)
ng=0

while abs(ok-ng)>0:
    cen=(ok+ng)//2

    cnt=0

    for a in alst:
        cnt+=(a+cen-1)//cen-1

    if cnt<=k:
        ok=cen
    else:
        ng=cen+1

print(ok)

Fixed submission:
n,k=list(map(int,input().split()))
alst=list(map(lambda x:int(x)*100,input().split()))

ok=max(alst)
ng=0

while abs(ok-ng)>1:
    cen=(ok+ng)//2

    cnt=0

    for a in alst:
        cnt+=(a+cen-1)//cen-1

    if cnt<=k:
        ok=cen
    else:
        ng=cen+1

if ok%100==0:
    print(ok//100)
else:
    print(ok//100+1)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

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

ok=max(alst)
ng=0

while abs(ok-ng)>0.01:
    cen=(ok+ng)/2

    cnt=0

    for a in alst:
        cnt+=(a+cen-1)//cen-1

    if cnt<=k:
        ok=cen
    else:
        ng=cen+0.01

print(int(np.ceil(ok)))


Fixed submission:
n,k=list(map(int,input().split()))
alst=list(map(lambda x:int(x)*100,input().split()))

ok=max(alst)
ng=0

while abs(ok-ng)>1:
    cen=(ok+ng)//2

    cnt=0

    for a in alst:
        cnt+=(a+cen-1)//cen-1

    if cnt<=k:
        ok=cen
    else:
        ng=cen+1

if ok%100==0:
    print(ok//100)
else:
    print(ok//100+1)
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=[int(c) for c in input()]

pc=sum(s)

resm=[0]*n
resp=[0]*n

jm=1
jp=1

totm=0
totp=0
for i in range(n):
    resm[n-i-1]=jm%(pc-1)
    resp[n-i-1]=jp%(pc+1)

    jm=(2*jm)%(pc-1)
    jp=(2*jp)%(pc+1)

    totm+=resm[n-i-1]*s[n-i-1]
    totm%=pc-1

    totp+=resp[n-i-1]*s[n-i-1]
    totp%=pc+1

def popc(x):
    return sum([int(c) for c in format(x,'b')])

for i in range(n):
    if s[i]==1:
        pcc=pc-1
        cres=(totm+pc-1-resm[i])%(pc-1)
    else:
        pcc=pc+1
        cres=(totp+resp[i])%(pc+1)
    
    if cres==0:
        print(1)
        continue

    cnt=1
    while cres>0:
        cres%=popc(cres)
        cnt+=1
    
    print(cnt)


Fixed submission:
n=int(input())
s=[int(c) for c in input()]

pc=sum(s)

resm=[0]*n
resp=[0]*n

jm=1
jp=1

totm=0
totp=0
for i in range(n):
    if pc-1>0:
        resm[n-i-1]=jm%(pc-1)
        jm=(2*jm)%(pc-1)
        totm+=resm[n-i-1]*s[n-i-1]
        totm%=pc-1
    
    resp[n-i-1]=jp%(pc+1)
    jp=(2*jp)%(pc+1)
    totp+=resp[n-i-1]*s[n-i-1]
    totp%=pc+1

def popc(x):
    return sum([int(c) for c in format(x,'b')])

for i in range(n):
    if s[i]==1:
        pcc=pc-1
        if pcc==0:
            print(0)
            continue
        cres=(totm+pc-1-resm[i])%(pc-1)
    else:
        pcc=pc+1
        cres=(totp+resp[i])%(pc+1)
    
    if cres==0:
        print(1)
        continue

    cnt=1
    while cres>0:
        cres%=popc(cres)
        cnt+=1
    
    print(cnt)