You are given the array of integer numbers a_0, a_1, ..., a_{n} - 1. For each element find the distance to the nearest zero (to the element which equals to zero). There is at least one zero element in the given array.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2·10^5) — length of the array a. The second line contains integer elements of the array separated by single spaces ( - 10^9 ≤ a_{i} ≤ 10^9).


-----Output-----

Print the sequence d_0, d_1, ..., d_{n} - 1, where d_{i} is the difference of indices between i and nearest j such that a_{j} = 0. It is possible that i = j.


-----Examples-----
Input
9
2 1 0 3 0 0 3 2 4

Output
2 1 0 1 0 0 1 2 3 
Input
5
0 1 2 3 4

Output
0 1 2 3 4 
Input
7
5 6 0 1 -2 3 4

Output
2 1 0 1 2 3 4

Difficulty: interview

Starter code:

Solutions:
inf = 10 ** 6
n = int(input())
a = list(map(int, input().split()))
dist = [inf] * n
for i in range(len(a)):
    if not a[i]:
        dist[i] = 0
        cur = 1
        i1 = i
        while i1 - 1 > - 1 and a[i1 - 1] != 0:
            dist[i1 - 1] = min(dist[i1 - 1], cur)
            i1 -= 1
            cur += 1
        i1 = i
        cur = 1
        while i1 + 1 < n and a[i1 + 1] != 0:
            dist[i1 + 1] = min(dist[i1 + 1], cur)
            i1 += 1
            cur += 1
print(*dist)

inf = 10**10
input()
nums = [int(x) for x in input().split()]

def run(ns):
    curr = inf
    res = []
    for num in ns:
        if num == 0:
            curr = 0
        res.append(curr)
        curr += 1
    return res

fw = run(nums)
rew = (run(reversed(nums)))[::-1]

print(' '.join(str(min(fw[i], rew[i])) for i in range(len(nums))))


#!/usr/bin/env python3

def main():
    try:
        while True:
            n = int(input())
            a = list(map(int, input().split()))
            b = [0] * n
            last = 400000
            for i in range(n - 1, -1, -1):
                if a[i] == 0:
                    last = i
                b[i] = last - i

            last = -400000
            for i in range(n):
                if a[i] == 0:
                    last = i
                print(min(i - last, b[i]), end=' ')
            print()

    except EOFError:
        pass

main()


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

ans = [n for _ in range(n)]
tmp = n
for i in range(n):
    if a[i] == 0:
        tmp = 0
    else:
        tmp += 1
    ans[i] = min(ans[i], tmp)

tmp = n
for i in range(n - 1, -1 , -1):
    if a[i] == 0:
        tmp = 0
    else:
        tmp += 1
    ans[i] = min(ans[i], tmp)

print(' '.join(map(str, ans)))



n = int(input())
l = list(map(int,input().split()))
zeroes = []
for i in range(len(l)):
    if l[i]==0:
        zeroes.append(i)
zero = -1
for i in range(n):
    zeroes.append(zeroes[-1])
s = ""
for i in range(len(l)):
    if i > zeroes[zero+1]:
        zero += 1
    if l[i]==0:
        s +=" 0"
    else:
        try:
            s += " "+str(min(abs(i-zeroes[zero]),abs(i-zeroes[zero+1]),abs(i-zeroes[zero+2])))
        except:
            s += " "+str(min(abs(zeroes[zero+1]-i),abs(i-zeroes[zero])))
print(s[1:])


import sys

inf = 1 << 30

def solve():
    n = int(input())
    a = [inf if ai != '0' else 0 for ai in input().split()]

    for i in range(n):
        if a[i] == 0:
            for j in range(i - 1, -1, -1):
                if a[j] > i - j:
                    a[j] = i - j
                else:
                    break

            for j in range(i + 1, n):
                if a[j] > j - i:
                    a[j] = j - i
                else:
                    break

    print(*a)

def __starting_point():
    solve()
__starting_point()

from collections import deque
import sys

# def search(matrix, inicial, dirs, final):
#     queue = deque()
#     queue.append(inicial)
#     matrix[inicial[0]][inicial[1]] = 0
#     while len(queue) > 0:
#         aux = queue.popleft()
# 
#         tupla = (aux[0], aux[1] + 1)
#         if matrix[tupla[0]][tupla[1]] != -1:
#             if matrix[tupla[0]][tupla[1]] == -9 or matrix[tupla[0]][tupla[1]] == -8:
#                 queue.append(tupla)
#                 matrix[tupla[0]][tupla[1]] = matrix[aux[0]][aux[1]] 
#                 
#                 dirs[tupla[0]][tupla[1]] = 'R'
#                 if dirs[tupla[0]][tupla[1]] != dirs[aux[0]][aux[1]]:
#                     matrix[tupla[0]][tupla[1]] += 1
#                                         
#         tupla = (aux[0], aux[1] - 1)
#         if matrix[tupla[0]][tupla[1]] != -1:        
#             if matrix[tupla[0]][tupla[1]] == -9 or matrix[tupla[0]][tupla[1]] == -8:
#                 queue.append(tupla)
#                 matrix[tupla[0]][tupla[1]] = matrix[aux[0]][aux[1]] 
#                 
#                 dirs[tupla[0]][tupla[1]] = 'L'
#                 if dirs[tupla[0]][tupla[1]] != dirs[aux[0]][aux[1]]:
#                     matrix[tupla[0]][tupla[1]] += 1           
#         
#         tupla = (aux[0] - 1, aux[1])        
#         if matrix[tupla[0]][tupla[1]] != -1:           
#             if matrix[tupla[0]][tupla[1]] == -9 or matrix[tupla[0]][tupla[1]] == -8:
#                 queue.append(tupla)
#                 matrix[tupla[0]][tupla[1]] = matrix[aux[0]][aux[1]] 
#                 
#                 dirs[tupla[0]][tupla[1]] = 'U'
#                 if dirs[tupla[0]][tupla[1]] != dirs[aux[0]][aux[1]]:
#                     matrix[tupla[0]][tupla[1]] += 1
#                     
#                         
#         tupla = (aux[0] + 1, aux[1])
#         if matrix[tupla[0]][tupla[1]] != -1:          
#             if matrix[tupla[0]][tupla[1]] == -9 or matrix[tupla[0]][tupla[1]] == -8:
#                 queue.append(tupla)
#                 matrix[tupla[0]][tupla[1]] = matrix[aux[0]][aux[1]] 
#                 
#                 dirs[tupla[0]][tupla[1]] = 'D'
#                 if dirs[tupla[0]][tupla[1]] != dirs[aux[0]][aux[1]]:
#                     matrix[tupla[0]][tupla[1]] += 1     
#                 
#     
# 
# 
# n, m = map(int, sys.stdin.readline().strip().split(" "))
# 
# matrix = []
# dirs = []
# aux = [-1 for i in range(m + 2)]
# matrix.append(aux)
# dirs.append(aux)
# 
# inicial = ()
# final = ()
# for i in range(n):
#     line = [-1] + list(sys.stdin.readline().strip()) + [-1]
#     matrix.append(line)
#     aux = [-1 for i in range(m + 2)]
#     dirs.append(aux)
#     for j in range(1, m + 1):
#         if line[j] == 'S':
#             inicial = (i + 1, j)
#         elif line[j] == 'T':
#             matrix[i + 1][j] = -8
#             final = (i + 1, j)
#         elif line[j] == '*':
#             matrix[i + 1][j] = -10
#         elif line[j] == '.':
#             matrix[i + 1][j] = -9        
#             
# aux = [-1 for i in range(m + 2)]
# matrix.append(aux)
# dirs.append(aux)
# 
# search(matrix, inicial, dirs, final)
# if matrix[final[0]][final[1]] <= 3 and matrix[final[0]][final[1]] >= 0:
#     print("YES")
# else:
#     print("NO")
    

n = int(sys.stdin.readline().strip())
array = list(map(int, sys.stdin.readline().strip().split(" ")))
zeros = [-float('Inf')]
for i in range(n):
    if array[i] == 0:
        zeros.append(i)
zeros.append(float('Inf'))
      
j = 1
for i in range(n):
    if array[i] == 0:
        j += 1
        print(array[i], end=" ")
    else:
        aux = min(abs(zeros[j] - i), abs(zeros[j - 1] - i))
        print(aux, end=" ")





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

    zero_i = None
    f = []
    for i, ai in enumerate(a):
        if ai == 0:
            zero_i = i

        if zero_i is None:
            f.append(n)
        else:
            f.append(i - zero_i)

    zero_i = None
    b = []
    for i, ai in enumerate(reversed(a)):
        if ai == 0:
            zero_i = i

        if zero_i is None:
            b.append(n)
        else:
            b.append(i - zero_i)

    res = (min(fi, bi) for fi, bi in zip(f, reversed(b)))
    for x in res:
        print(x, end=' ')


def __starting_point():
    main()

__starting_point()

BIG = 10000000000

def main(n, arr):
    dist = BIG
    res = []
    for x in arr:
        if x == 0:
            dist = 0
        elif dist != BIG:
            dist += 1
        res.append(dist)

    dist = BIG
    for i in range(len(arr)-1, -1, -1):
        x = arr[i]
        if x == 0:
            dist = 0
        elif dist != BIG:
            dist += 1

        if res[i] > dist:
            res[i] = dist

    print(' '.join(map(str, res)))




n = int(input())
arr = [int(x) for x in input().split()]
main(n, arr)


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

x = [0]*len(a)
y = [0]*len(a)

c1 = 0
z1 = False
c2 = 0
z2 = False

for i in range(len(a)):
    if a[i] == 0:
        z1 = True
        c1 = 1
    elif z1:
        x[i] = c1
        c1+=1
    else:
        x[i] = 0

    if a[n-i-1] == 0:
        z2 = True
        c2 = 1
    elif z2:
        y[n-i-1] = c2
        c2+=1
    else:
        y[n-i-1] = 0

ans = ""
for i in range(len(a)):
    if (x[i] == 0):
        if y[i] == 0:
            ans += "0 "
        else:
            ans += str(y[i]) + " "
    else:
        if y[i] == 0:
            ans += str(x[i]) + " "
        else:
            ans += str(min(x[i], y[i])) + " "
print(ans)
            

        


def qa():
    n, k = map(int, input().split())
    if k > n :
        print('-1')
        return
    matrix = [[0]*n for _ in range(n)]
    for i in range(k):
        matrix[i][i] = 1
    for line in matrix:
        print(' '.join(map(str,line)))
def qb():
    _ = input()
    d = [*map(int,input().split())]
    zeroIndex = [0 if v == 0 else len(d) for i, v in enumerate(d) ]
    counter = len(d)
    for i in range(len(d)):
        if zeroIndex[i] == 0:
            counter = 0
            continue
        counter += 1
        zeroIndex[i] = min(counter, zeroIndex[i])
    counter = len(d)
    for i in range(len(d)-1,-1,-1):
        if zeroIndex[i] == 0:
            counter = 0
            continue
        counter += 1
        zeroIndex[i] = min(counter, zeroIndex[i])
    print(' '.join(map(str,zeroIndex)))
qb()

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

dist = pow(10,9)
d=[dist]*len(a)

for i in range(len(a)):
    if(a[i]==0):
        d[i]=0
        dist = 0
    elif(dist < d[i]):
        dist+=1
        d[i] = dist

for i in range(len(a)-1,-1,-1):
    #print(dist)
    if(a[i]==0):
        d[i]=0
        dist = 0
    elif(dist + 1 < d[i]):
        dist+=1
        d[i] = dist
for i in d:
    print(str(i)+' ',end='')


from math import *
length=int(input())
a=list(map(int,input().strip().split()))
p=[-inf]
for i in range(length):
    if a[i]==0:
        p.append(i)
p.append(inf)
i=0
j=1
b=[0 for _ in range(length)]
for k in range(length):
    if k<p[j]:
        b[k]=min(k-p[i],p[j]-k)
    if k==p[j]:
        j+=1
        i+=1
for i in b:
    print(i,end=' ')


n  = int(input())

l = list(map(int, input().split()))
ans = [400001 for i in range(n)]
zs=[]
for x in range(n):
    if l[x]==0:
        zs.append(x)
        ans[x]=0

for i in zs:
    lp=i-1
    rp=i+1
    cntL=1
    cntR=1
    while lp!=-1:
        
        if ans[lp]<=cntL:
            break
        ans[lp]=cntL
        cntL+=1
        lp-=1
    while rp!=n:
        if ans[rp]<=cntR:
            break
        ans[rp]=cntR
        cntR+=1
        rp+=1
         
print(' '.join([str(x) for x in ans]))


def Posicion(L):
    i = 1
    A = L
    for k in range (len(L)):
        if L[k]!=0:
            A[k]=i
            i +=1
        else:
            i=1
    return A     
def SepararDerecha(L):
    B=[]
    Mayork = 0
    for k in range (len(L)):
        if L[k]==0:
            if k > Mayork:
                Mayork = k
    c = Mayork+1
    while c < len(L):
        B.append(L[c])
        c += 1
    return B
def SepararIzquierda(L):
    B = []
    k = 0
    while L[k]!=0:
        B.append(L[k])
        k += 1
    return B
def Invertir(L):
    B =[]
    k=len(L)-1
    while k>=0:
        B.append(L[k])
        k -=1
    return B    
N = int(input())
L = input()
L = L.split()
A = []
for k in range (len(L)):
    A.append(int(L[k]))
PI = SepararIzquierda(A)
z = len(PI)
PIII = []
for k in range (len(PI)):
    PIII.append(z)
    z-=1
pizquierda = len(PIII)
PD = SepararDerecha(A)
PD = Posicion(PD)
pderecha = len(PD)
D = []
for k in range (pizquierda,len(A)-pderecha):
    D.append(A[k])
AI = Posicion(D)
AD =  Invertir(D)
AD = Posicion(AD)
AD = Invertir(AD)
B = []
for k in range (len(AD)):
    if AD[k] < AI[k]:
        B.append(AD[k])
    else:
        B.append(AI[k])
C =[]
for k in range (len(PIII)):
    C.append(PIII[k])
for k in range (len(B)):
    C.append(B[k])
for k in range (len(PD)):
    C.append(PD[k])
Respuesta = str(C[0])
for k in range (1,len(C)):
    Respuesta += ' ' + str(C[k])
print(Respuesta)


#!/usr/bin/env python3
from sys import stdin,stdout

def ri():
    return list(map(int, stdin.readline().split()))
#lines = stdin.readlines()

n = int(input())
a = list(ri())

for i in range(n):
    if a[i] != 0:
        a[i] = -1

for i in range(n):
    if a[i] != 0:
        continue
    for j in range(i+1, n):
        if a[j] == 0:
            break
        if a[j] == -1 or a[j] > j-i:
            a[j] = j-i
    for j in range(i-1, -1, -1):
        if a[j] == 0:
            break
        if a[j] == -1 or a[j] > i-j:
            a[j] = i-j

print(" ".join(map(str, a)))


n = int(input())
nums = [int(x) for x in input().split(' ')]
firstZero = nums.index(0)
lastZero = len(nums) - 1 - nums[::-1].index(0)

for i in range(len(nums[firstZero:])):
	if nums[firstZero + i] == 0:
		c = 0
	else:
		c += 1
	nums[firstZero + i] = c
nums = nums[::-1]
for i in range(len(nums)):
	if nums[i] == 0:
		c = 0
	else:
		c += 1

	if i > len(nums) - firstZero:
		nums[i] = c
		continue
	
	if nums[i] >= c or nums[i] < 0:
		nums[i] = c 

print(' '.join([str(x) for x in nums[::-1]]))

import math
n = int(input())
data = []
data = list(map(int,input().split()))
l = [0] * n
r = [0] * n
p = 2 * n
p1 = 2 * n
s = ''
for i in range(n):
    l[i] = p
    if data[i] == 0:
        p = i
    
for i in range(n - 1,-1, -1):
    r[i] = p1
    if data[i] == 0:
        p1 = i 

for i in range(n): 
    if data[i] != 0:
        print(min(abs((l[i] - i)),abs((r[i] - i))), end = ' ')
    else:
        print(0, end = ' ')
        

    


n = int(input())
arr = input().split(' ')


last_zeros = [0]*n
last_zero = -1
for i in range(n):
    arr[i] = int(arr[i])
    if arr[i] == 0:
        last_zero = i
    if last_zero == -1:
        last_zeros[i] = 10**10
    else:
        last_zeros[i] = i - last_zero

last_zero = -1
for i in reversed(range(n)):
    if arr[i] == 0:
        last_zero = i
    if last_zero != -1:
        last_zeros[i] = min(last_zeros[i], last_zero - i)

for el in last_zeros:
    print(el, end=' ')

n=int(input())
a=list(input().split())
b=[i for i in range(n) if a[i]=="0"]
c=""
j=0
for i in range(n):
    if b[0]>=i:
        t=b[0]-i
        c+="{} ".format(t)
    elif j!=len(b)-1:
        t=min(abs(i-b[j]),abs(i-b[j+1]))
        if t==0:
            j+=1
        c+="{} ".format(t)
    else:
        c+="{} ".format(i-b[j])
print(c)
    


import sys

inf = 1 << 30

def solve():
    n = int(input())
    a = [int(i) for i in input().split()]

    ans = [inf]*n

    d = inf

    for i in range(n):
        if a[i] == 0:
            d = 0

        ans[i] = d
        d += 1

    d = inf

    for i in reversed(range(n)):
        if a[i] == 0:
            d = 0

        ans[i] = min(ans[i], d)
        d += 1

    print(*ans)

def __starting_point():
    solve()
__starting_point()

n=int(input())
a=list(map(int,input().split()))
l,r,ll,rr,c=[0]*n,[0]*n,-10**9,10**9,[]
for i in range(n):
  if not a[i]:ll=i
  l[i]=i-ll
for i in range(n-1,-1,-1):
  if not a[i]:rr=i
  r[i]=rr-i
for i in range(n):c.append(str(min(l[i],r[i])))
print(' '.join(c))


import sys
import math
n = int(input())
a = list(map(int, input().split()))
ans = [n for i in range(n)]
lind = -n
for i in range(n):
    if a[i] == 0:
        lind = i
    ans[i] = min(ans[i], abs(i - lind))
lind = -n
for i in range(n - 1, -1, -1):
    if a[i] == 0:
        lind = i
    ans[i] = min(ans[i], abs(i - lind))
for  i in range(n):
    print(ans[i], end  = " " )

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

inf = 10 ** 9
ans = [inf] * n
l = inf
for i in range(n):
    if not a[i]:
        l = 0
    
    ans[i] = min(ans[i], l)
    l += 1

l = inf
for i in range(n - 1, -1, -1):
    if not a[i]:
        l = 0
    
    ans[i] = min(ans[i], l)
    l += 1
    
print(' '.join(map(str, ans)))