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

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

ans = 0
for i in range(n-1):
    ans = (ans + A[i] * sum(A[i+1:])) % int(1e9 + 7)

print(ans)


### FIXED CODE ###

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

s = sum(A)
ans = 0
for i in range(n-1):
    s -= A[i]
    ans = (ans + A[i] * s) % int(1e9 + 7)

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

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


def xor(x, y):
    X = bin(max(x, y))[2:]
    Y = bin(min(x, y))[2:]
    w = str(int(X)+int(Y))
    ans = ""
    for i in range(len(w)):
        if w[i] != "1":
            w = w[:i] + "0" + w[i+1:]
    return int("0b" + w, 2)


Ans = 0
mod = 10**9 + 7
for i in itertools.combinations(a, 2):
        Ans = (Ans + xor(i[0], i[1])) % mod
print(Ans)


### FIXED CODE ###

def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = tuple(map(int, input().split()))
mod = 10**9 + 7
cnt = [0] * 60
for i in range(n):
    r = a[i]
    for j in range(60):
        if r & 1:
            cnt[j] += 1
        r >>= 1

ans = 0
for i in range(60):
    ans += powmod(2, i, mod) * cnt[i] * (n-cnt[i])
    ans %= mod
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in [0] * q:
    l, r = map(int, input().split())
    t = s[l-1:r]
    print(t.count("AC"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac = [0] * (n + 1)
for i in range(n):
    ac[i + 1] = ac[i] + (1 if s[i:i + 2] == "AC" else 0)
for i in [0] * q:
    l, r = map(int, input().split())
    print(ac[r-1] - ac[l-1])
### BUGGY CODE ###

n = int(input())
L = input()

S = set()
cnt = 0
for i in range(1000):
    i = str(i).zfill(3)
    num = 0
    for j in range(n):
        if L[j] == i[0] and num == 0:
            num =1
        elif L[j] == i[1] and num == 1:
            num =2
        elif L[j] == i[2] and num == 2:
            S.add(i)
            
print(len(S))

### FIXED CODE ###

n = int(input())
s = input()

S = set()
cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            dig = 1
            t = str(i)+str(j)+str(k)

            for r in range(n):
                if dig == 1 and t[0] == s[r]:
                    dig +=1

                elif dig == 2 and t[1] == s[r]:
                    dig +=1
                    
                elif dig == 3 and t[2] == s[r]:
                    S.add(t)

print(len(S))
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
from sys import stdin

N, M = map(int, input().split())
A = list(map(int, stdin.readline().split()))
heapify(A)
BC = [None] * M
for i in range(M):
    BC[i] = tuple(map(int, stdin.readline().split()))
BC = sorted(BC, key=lambda x: x[1])

for bc in BC:
    for i in range(bc[0]):
        if bc[1] <= A[0]:
            break
        heappop(A)
        heappush(A, bc[1])

print(sum(A))


### FIXED CODE ###

from heapq import heapify, heappop, heappush
from sys import stdin

N, M = map(int, input().split())
A = list(map(int, stdin.readline().split()))
heapify(A)
BC = [None] * M
for i in range(M):
    BC[i] = tuple(map(int, stdin.readline().split()))
BC = sorted(BC, key=lambda x: x[1], reverse=True)

enough = False
for bc in BC:
    if enough:
        break
    for i in range(bc[0]):
        if bc[1] <= A[0]:
            enough = True
            break
        heappop(A)
        heappush(A, bc[1])

print(sum(A))
### BUGGY CODE ###

N = int(input())

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table

S = 0
for k in range(1, N + 1):
    S += k * num_divisors_table(k)[k]
print(S)


### FIXED CODE ###

N = int(input())

S = 0
for i in range(1, N + 1):
    n = N // i
    S += i * (n * (n + 1) // 2)
print(S)
### BUGGY CODE ###

N = int(input())
P = [-1]
P += list(map(int, input().split(' ')))
count = 0
for i in range(1,N+1):
    boolean = True
    for j in range(1, i):
        if P[i] > P[j]:
            boolean = False
            break
    if boolean:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
P = [-1]
P += list(map(int, input().split(' ')))
mini = 10 ** 9
count = 0
for i in range(1,N+1):
    if P[i] <= mini:
        mini = P[i]
        count += 1
print(count)
### BUGGY CODE ###

S = input()
s = 0
e = s + 4
ans = 0
loop = False

while True:
    
    if loop == False:
        index = int(S[s:e])
        if index % 2019 == 0:
            ans += 1
            loop = True
            s_cp = s
            e_cp = e
        else:
            e += 1
    else:
        s2 = e_cp
        e2 = s2+e_cp-s_cp
        if S[s:e] == S[s2:e2]:
            ans += 1
            s_cp = s2
            e_cp = e2
        else:
            loop = False
            e += 1
    if e > len(S) :
        s += 1
        e = s + 4
        if e > len(S): break

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
S = input()[::-1]

mod = [0]*2019
mod[0] = 1
ten = 1
index = 0
for s in S:
    index += ten*int(s)
    index %= 2019
    mod[index] += 1
    ten *= 10
    ten %= 2019

ans = 0
for m in mod:
    ans += m * (m-1) // 2

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

import sys
sys.setrecursionlimit(10001)

def dfs(u, g, stack):
    visited[u] = True
    for v in g[u]:
        if not visited[v]:
            dfs(v, g, stack)
    stack.append(u)
    return stack

nv, ne = map(int, input().split(' '))
adj, tps = ([[] for _ in range(nv)] for _ in range(2))

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)
    tps[t].append(s)

visited = [False] * nv
stack = []
for i in range(nv):
    if not visited[i]:
        stack = dfs(i, adj, stack)

visited = [False] * nv
comps = []
while stack:
    i = stack.pop()
    if not visited[i]:
        comp = dfs(i, tps, [])
        comps.append(comp)

nv = int(input())
for _ in range(nv):
    u, v = map(int, input().split(' '))
    ans = 0

    for comp in comps:
        if u in comp and v in comp:
            ans = 1

    print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10001)

def dfs(u, g, stack):
    visited[u] = True
    for v in g[u]:
        if not visited[v]:
            dfs(v, g, stack)
    stack.append(u)
    return stack

nv, ne = map(int, input().split(' '))
adj, tps = ([[] for _ in range(nv)] for _ in range(2))

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)
    tps[t].append(s)

visited = [False] * nv
stack = []
for i in range(nv):
    if not visited[i]:
        stack = dfs(i, adj, stack)

visited = [False] * nv
comp_is = {}
while stack:
    i = stack.pop()
    if not visited[i]:
        comp = dfs(i, tps, [])
        for v in comp:
            comp_is[v] = i

nv = int(input())
for _ in range(nv):
    u, v = map(int, input().split(' '))
    if comp_is[u] == comp_is[v]: print(1)
    else: print(0)
### BUGGY CODE ###

X,Y = map(int, input().split())

a = X
A = []
A.append(a)

flg = 0
count = 2
while flg!=1:
    e = count*a
    if e>Y:
        flg = 1
        break
    count = count + 1
    if e%A[len(A)-1]==0:
        A.append(e)

print(len(A))

    

### FIXED CODE ###

import math

X,Y = map(int, input().split())

ans = []
for i in range(0, int(math.log2(10**18))+1):
    Z = X*pow(2, i)
    if Z<=Y:
        ans.append(Z)

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

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

def search_wb():
    sub = 1
    max_abs = abs(A[0] - sub)
    for a in A:
        if max_abs < abs(a - sub):
            max_abs = abs(a-sub)
        sub += 1
    return max_abs, -max_abs

def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


maxb, minb= search_wb()

while abs(maxb - minb) > 1:
    mid = (maxb + minb) // 2
    #print("max{} min{} mid{}".format(maxb, minb, mid))
    if sunuke(mid) >  sunuke(mid + 1):
        minb = mid
    else:
        maxb = mid


mins = sunuke(minb)
maxs = sunuke(maxb)
if mins < maxs:
    print(mins)
else:
    print(maxs)



### FIXED CODE ###

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

def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


B = []

sub = 1
for a in A:
    b = a - sub
    B.append(b)
    sub += 1

B.sort()
b1 = N // 2
if N < 3:
    print(sunuke(B[b1]))
    exit()

b2 = b1 + 1
b1_s = sunuke(B[b1])
b2_s = sunuke(B[b2])
if b1_s < b2_s:
    print(b1_s)
else:
    print(b2_s)
### BUGGY CODE ###

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

x = range(L, R + 1)

minimum = 2018
for i in range(len(x) - 1):
  for j in range(i + 1, len(x)):
    minimum = min(minimum, x[i] * x[j] % 2019)

print(minimum)

### FIXED CODE ###

L, R = list(map(int, input().split(' ')))
#print(L, R)

min = 2019
for i in range(L, R):
    for j in range(i + 1, R + 1):
        mod_ij = (i * j) % 2019
        if min > mod_ij:
            min = mod_ij
            if min == 0:
                break
    if min == 0:
        break

print(min)
### BUGGY CODE ###

N=int(input())

S=[]
for i in range(N):
	x=input()
	if x not in S:
		S.append(x)

print(len(S))

### FIXED CODE ###

import collections

N=int(input())

S=[]
for i in range(N):
		S.append(input())

print(len(collections.Counter(S)))
### BUGGY CODE ###

import itertools

N = int(input())
Lmat = [int(n) for n in input().split()]
Lmat.sort()

import time
start = time.time()

def binary_search_nearest(list, item):#もっとも近い値のindexをbsで探して返す関数
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return low-1

def iftriangle(first,second,third):
    if third < len(Lmat):
        if Lmat[first]>=Lmat[second]+Lmat[third]:
            return 0
        elif Lmat[second]>=Lmat[first]+Lmat[third]:
            return 0
        elif Lmat[third]>=Lmat[first]+Lmat[second]:
            return 0
        else:
            #print([first,second,third])
            return 1
    else:
        return 0

sum = 0
for i in range(N):
    for j in range(i+1,N):
        min_index = j
        max_index = binary_search_nearest(Lmat, Lmat[i]+Lmat[j])#これだとjustの値しか取得できない=>bs自体を実装する必要がある
        #print(binary_search_nearest(Lmat, Lmat[patern[0]]+Lmat[patern[1]]))#これだとjustの値しか取得できない=>bs自体を実装する必要がある)
        for Lk_index in range(min_index+1,max_index+1):
            sum += iftriangle(i,j,Lk_index)#ここは1に置き換え不可。計算が必要


print(sum)

elapsed_time = time.time() - start
#print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")



### FIXED CODE ###

import time
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)

start = time.time()
res = 0
for i in range(n):
    for j in range(i+1,n):
        ab = l[i] + l[j]
        c_index = bisect_left(l, ab)
        res += c_index - j - 1
print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
List = [0]*N

for i in range(N):
  List[i] = str(A.index(i+1)+1)



print(' '.join(List))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
List = [0]*N


for i, a in enumerate(A):
  List[int(a)-1] = str(i+1)

  
print(" ".join(List))
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    # 全部0の最遅ケースでもlog(N)*2くらいで収束する log(2*10**5)<50
    for _ in range(min(K, 50)):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            b[i+1] = tmp[i] + b[i]
        for i in range(N):
            A[i] = b[i+1] 
        # print(A)

    print(*A)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    # 全部0の最遅ケースでもlog(N)*2くらいで収束する log(2*10**5)<50
    for _ in range(min(K, 50)):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            b[i+1] = tmp[i] + b[i]
        for i in range(N):
            A[i] = b[i+1] 
        # print(A)

    print(*A)

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

import math

inn = [int(x) for x in input().split()]
aa = []
bb = []
for i in range(inn[0]):
    tmp = [int(x) for x in input().split()]
    aa.append(tmp[0])
    bb.append(tmp[1])

count = 0
tot = 0
ba = list(filter((lambda x: x > max(aa)), bb))
if sum(ba) == inn[1]:
    print(len(ba))
    exit()
elif sum(ba) > inn[1]:
    for b in sorted(ba, reverse=True):
        tot += b
        count += 1
        if tot >= inn[1]:
            print(count)
            exit()
else:
    tot = sum(ba)
    count = len(ba) + math.ceil((inn[1]-tot)/max(aa))
    print(count)


### FIXED CODE ###

import math

inn = [int(x) for x in input().split()]
aa = []
bb = []
for i in range(inn[0]):
    tmp = [int(x) for x in input().split()]
    aa.append(tmp[0])
    bb.append(tmp[1])

maxaa = max(aa)
ba = [x for x in bb if x > maxaa]
sumba = sum(ba)
lenba = len(ba)
if sumba == inn[1]:
    print(lenba)
    exit()
elif sumba > inn[1]:
    count = lenba
    tot = sumba
    for b in sorted(ba):
        tot -= b
        if tot < inn[1]:
            print(count)
            exit()
        count -= 1
else:
    count = lenba + math.ceil((inn[1]-sumba)/max(aa))
    print(count)
### BUGGY CODE ###

N = int(input())
my_list = [None] * N
for i in range(N):
    s_i = sorted(list(input()))
    my_list[i] = s_i
sum = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(10):
            if not(my_list[i][k] == my_list[j][k]):
                break
            elif k == 9:
                sum += 1
print(sum)


### FIXED CODE ###

n = int(input())
dict = {}
ans = 0

for i in range(n):
    s = str(sorted(input()))
    if s in dict.keys():
        ans += dict[s]
        dict[s] += 1
    else:
        dict[s] = 1
print(ans)
### BUGGY CODE ###

Ns,Ms=input().split()
N=int(Ns)
M=int(Ms)
LR=input().split()
ans=set(list(range(int(LR[0]),int(LR[1])+1)))
for i in range(M-1):
	LR=[]
	LR=input().split()
#	print("ssssssssss")
#	print(ans)
	ansy=set(list(range(int(LR[0]),(int(LR[1])+1))))
	ans=ans&ansy
ansx=list(ans)
print(len(ans))


### FIXED CODE ###

Ns,Ms=input().split()
N=int(Ns)
M=int(Ms)
lists=[]
ansmins,ansmaxs=input().split()
ansmin=int(ansmins)
ansmax=int(ansmaxs)
for i in range(M-1):
	tmpmin,tmpmax=input().split()
	if int(tmpmin)>ansmin:
		ansmin=int(tmpmin)
	if int(tmpmax)<ansmax:
		ansmax=int(tmpmax)

if (ansmax-ansmin+1)<0:
	ans=0
else:
	ans=ansmax-ansmin+1
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import heapq

def main():
    H, W, M = map(int, readline().split())
    m = map(int,read().split())
    hw = list(zip(m,m))

    bR = [0] * (H+1)
    bC = [0] * (W+1)

    maxes = []
    x = [[False] * (W+1) for i in range(H+1)]

    for (h, w) in hw:
        bR[h] += 1
        bC[w] += 1
        x[h][w] = True

    rmax = max(bR)
    cmax = max(bC)
    rmis = [i for i in range(H+1) if bR[i] == rmax]
    cmis = [i for i in range(W+1) if bC[i] == cmax]

    ans = rmax + cmax
    minus_flag = True
    for r in rmis:
        for c in cmis:
            if not x[r][c]:
                minus_flag = False
                break
    if minus_flag:
        ans -= 1

    
    # print(hw)
    # print(bR, bC)
    # print(rmax, cmax, rmis, cmis)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import heapq

def main():
    H, W, M = map(int, readline().split())
    m = map(int,read().split())
    hw = list(zip(m,m))

    row_bombers = [0] * (H+1)
    col_bombers = [0] * (W+1)

    for (h, w) in hw:
        row_bombers[h] += 1
        col_bombers[w] += 1

    row_max = max(row_bombers)
    col_max = max(col_bombers)

    max_rows = [i for i in range(H+1) if row_bombers[i] == row_max]
    max_cols = [i for i in range(W+1) if col_bombers[i] == col_max]

    ans = row_max + col_max
    
    num_empty_cells_in_kouho = len(max_rows) * len(max_cols)
    for (h, w) in hw:
        if row_bombers[h] == row_max and col_bombers[w] == col_max:
            num_empty_cells_in_kouho -= 1

    if num_empty_cells_in_kouho == 0:
        ans -= 1
    
    print(ans)


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

x,y,z,k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
#a.sort(reverse=True)
#b.sort(reverse=True)
c.sort(reverse=True)
E = [0] * x*y

total = [0] * (x*y + z*k)
idx = 0
for i in range(x):
      for j in range(y):
            E[idx] = a[i] + b[j]
            idx += 1
E.sort(reverse=True)
idx = 0
for i in range(min(x*y,k)):
      for j in range(min(z,k)):
            total[idx] = E[i] + c[j]
            idx += 1

total.sort(reverse=True)
for i in range(k):
      print(total[i])


### FIXED CODE ###

x,y,z,K = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

abc = []

for i in range (x):
      for j in range(y):
            for(k) in range(z):
                  if (i+1)*(j+1)*(k+1) <= K:
                        abc.append(a[i]+b[j]+c[k])
                  else:
                        break

abc.sort(reverse=True)
for i in abc[:K]:
      print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    N = II()
    l_list = LI()

    # 短い順
    l_list = sorted(l_list)
    ind_list = list(range(len(l_list)))

    from bisect import bisect_left, bisect_right
    from itertools import combinations
    dprint(l_list)
    cnt = 0
    for a, b in combinations(ind_list, 2):
        # 2つえらぶ
        # 残りでできたl_listを作る
        cand_list = []
        for c in range(len(l_list)):
            if c != a and c!= b:
                cand_list.append(l_list[c])

        # cのmax, min
        la = l_list[a]
        lb = l_list[b]

        mx = la + lb
        mn = max(la, lb) - min(la, lb)

        # cand_listをbisectする
        right_ind_plus1 = bisect_left(cand_list, mx)
        left_ind = bisect_right(cand_list, mn)

        dprint(la, lb, mn, mx, cand_list, left_ind, right_ind_plus1, cnt)
        cnt += right_ind_plus1 - left_ind

    print(cnt//3)

solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    N = II()
    l_list = LI()

    # 短い順
    l_list = sorted(l_list)
    ind_list = list(range(len(l_list)))

    from bisect import bisect_left, bisect_right
    from itertools import combinations
    dprint(l_list)
    cnt = 0
    for a, b in combinations(ind_list, 2):
        # 2つえらぶ

        # 残りでできたl_listを作る
        # cand_list = []
        # for c in range(len(l_list)):
        #     if c != a and c!= b:
        #         cand_list.append(l_list[c])

        # cのmax, min
        la = l_list[a]
        lb = l_list[b]

        mx = la + lb
        mn = max(la, lb) - min(la, lb)

        # cand_listをbisectする
        right_ind_plus1 = bisect_left(l_list, mx)
        left_ind = bisect_right(l_list, mn)

        # dprint(la, lb, mn, mx, l_list, left_ind, right_ind_plus1, cnt)

        cnt += right_ind_plus1 - left_ind

        if left_ind <= a and a < right_ind_plus1:
            cnt -= 1

        if left_ind <= b and b < right_ind_plus1:
            cnt -= 1

    print(cnt//3)

solve()
### BUGGY CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
S = readline().decode().rstrip()
one_cnt = S.count('1')
cnt = [0]*(one_cnt+1)
pop_cnt = [0]* (N+1)
for i in range(1,one_cnt+1):
    pop_cnt[i] = pop_cnt[i//2] + i%2
    j = i % pop_cnt[i]
    cnt[i] = 1 + cnt[j] 
    
n = int(S, 2)
for i in range(N):
    if S[i] == '1':
        tmp = n - 2**(N-i-1)
        if tmp == 0:
            print(0)
        else:
            tmp %= (one_cnt-1)
            print(1+cnt[tmp])
    else:
        tmp = n + 2**(N-i-1) 
        tmp %= (one_cnt+1)
        print(1+cnt[tmp])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
S = readline().decode().rstrip()
one_cnt = S.count('1')
S_rev = S[::-1]
#one_modは元のビットが立ってるとき zero_modは逆
one_mod = 0
zero_mod = 0
#Nが大きすぎるため下の桁から順に計算
for i in range(N):
    if S_rev[i] == '1' and one_cnt - 1 != 0:
        one_mod += pow(2,i,one_cnt - 1)
        one_mod %= (one_cnt - 1)
        zero_mod += pow(2,i,one_cnt + 1)
        zero_mod %= (one_cnt + 1)

cnt = [0]*(one_cnt+1)
pop_cnt = [0]* (one_cnt+1)
for i in range(1,one_cnt+1):
    pop_cnt[i] = pop_cnt[i//2] + i%2
    j = i % pop_cnt[i]
    cnt[i] = 1 + cnt[j] 

one_pow2 = [1]*(N+1)
zero_pow2 = [1]*(N+1)
for i in range(1,N):
    if one_cnt-1 != 0:
        one_pow2[i+1] = one_pow2[i]*2 % (one_cnt - 1)
    zero_pow2[i+1] = zero_pow2[i]*2 % (one_cnt + 1)

for i in range(N):
    if S[i] == '1':
        if one_cnt-1 == 0:
            print(0)
        else:
            nxt = one_mod
            nxt -= one_pow2[N-i]
            nxt %= (one_cnt - 1)
            print(1+cnt[nxt])
    else:
        nxt = zero_mod
        nxt += zero_pow2[N-i]
        nxt %= (one_cnt + 1)
        print(1+cnt[nxt])