Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
        for diff in (-1, 1, -n, n):
            ppos = diff+pos
            if ppos<0 or ppos>=n*n:
                continue
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
#         if pos+n<n*n:
#             ppos = pos + n
#             if d[ppos]>v:
#                 d[ppos] = v
#                 nv = v+1 if not vacant[ppos] else v
#                 q.append((nv, ppos))
#         if pos-n>=0:
#             ppos = pos - n
#             if d[ppos]>v:
#                 d[ppos] = v
#                 nv = v+1 if not vacant[ppos] else v
#                 q.append((nv, ppos))
#         if pos+1<n*n:
#             ppos = pos + 1
#             if d[ppos]>v:
#                 d[ppos] = v
#                 nv = v+1 if not vacant[ppos] else v
#                 q.append((nv, ppos))
#         if pos-1>=0:
#             ppos = pos - 1
#             if d[ppos]>v:
#                 d[ppos] = v
#                 nv = v+1 if not vacant[ppos] else v
#                 q.append((nv, ppos))
print(ans)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    v = d[pos]
    vacant[pos] = True
    q = [(v, pos)]
    while q:
        v,pos = q.pop()
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
print(ans)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    v = d[pos]
    vacant[pos] = True
    q = [(v, pos)]
    while q:
        v,pos = q.pop()
        for diff in (-n, n, -1, 1):
            ppos = pos + diff
            if ppos<0 or ppos>=n*n:
                continue
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
print(ans)


Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

def sub(pos):
    v = d[pos]
    q = [(v, pos)]
    while q:
        v,pos = q.pop()
        for diff in (-n, n, -1, 1):
            ppos = pos + diff
            if ppos<0 or ppos>=n*n:
                continue
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
ans = 0
for v in p:
    v -= 1
    ans += d[v]
    sub(v)
    vacant[v] = True
print(ans)


Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from numba import njit, jit, int32
import numpy as np
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
# p = list(map(int, input().split()))
p = np.array(input().split(), dtype=np.int32)


@njit('(i4,i4[::1])', cache=True)
def main(n, p):
#     d = [[None]*n for _ in range(n)]
    d = np.zeros((n,n), dtype=np.int32)
    for i in range(n):
        for j in range(n):
            d[i,j] = min(i, n-1-i, j, n-1-j)
#     vacant = [[False]*n for _ in range(n)]
    vacant = np.zeros((n,n), dtype=np.int32)

    ans = 0
    for v in p:
        v -= 1
        x,y = v//n, v%n
        ans += d[x,y]
    #     print(v, d[x][y], d)
        v = d[x,y]
        q = [(v, x, y)]
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        while q:
            v,i,j = q.pop()
            for xx, yy in zip(dx,dy):
                ii = i+xx
                jj = j+yy
                if ii<0 or jj<0 or ii>=n or jj>=n:
                    continue
                if d[ii,jj]>v:
                    d[ii,jj] = v
                    nv = v+1 if not vacant[ii,jj] else v
                    q.append((nv, ii, jj))

        vacant[x,y] = 1
    return ans
ans = main(n,p)
print(ans)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)

Buggy python submission (verdict: Runtime Error):
from numba import njit, jit, int32
import numpy as np
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
# p = list(map(int, input().split()))
p = np.array(input().split(), dtype=np.int32)


@njit('(i4,i4[::1])', cache=True)
def main(n, p):
#     d = [[None]*n for _ in range(n)]
    d = np.zeros((n,n), dtype=np.int32)
    for i in range(n):
        for j in range(n):
            d[i,j] = min(i, n-1-i, j, n-1-j)
#     vacant = [[False]*n for _ in range(n)]
    vacant = np.zeros((n,n), dtype=np.int32)

    ans = 0
    for v in p:
        v -= 1
        x,y = v//n, v%n
        ans += d[x,y]
    #     print(v, d[x][y], d)
        v = d[x,y]
        q = [(v, x, y)]
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        while q:
            v,i,j = q.pop()
            for xx, yy in zip(dx,dy):
                ii = i+xx
                jj = j+yy
                if ii<0 or jj<0 or ii>=n or jj>=n:
                    continue
                if d[ii,jj]>v:
                    d[ii,jj] = v
                    nv = v+1 if not vacant[ii,jj] else v
                    q.append((nv, ii, jj))

        vacant[x,y] = 1
    return ans
ans = main(n,p)
print(ans)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [[None]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        d[i][j] = min(i, n-1-i, j, n-1-j)
vacant = [[False]*n for _ in range(n)]
from numba import njit
@njit('(i4,i4)', cache=True)
def sub(x,y):
    v = d[x][y]
    q = [(v, x, y)]
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    while q:
        v,i,j = q.pop()
        for xx, yy in zip(dx,dy):
            ii = i+xx
            jj = j+yy
            if ii<0 or jj<0 or ii>=n or jj>=n:
                continue
            if d[ii][jj]>v:
                d[ii][jj] = v
                nv = v+1 if not vacant[ii][jj] else v
                q.append((nv, ii, jj))
ans = 0
for v in p:
    v -= 1
    x,y = v//n, v%n
    ans += d[x][y]
#     print(v, d[x][y], d)
    sub(x,y)
    vacant[x][y] = True
print(ans)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [[None]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        d[i][j] = min(i, n-1-i, j, n-1-j)
vacant = [[False]*n for _ in range(n)]
from numba import njit
@njit
def sub(x,y):
    v = d[x][y]
    q = [(v, x, y)]
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    while q:
        v,i,j = q.pop()
        for xx, yy in zip(dx,dy):
            ii = i+xx
            jj = j+yy
            if ii<0 or jj<0 or ii>=n or jj>=n:
                continue
            if d[ii][jj]>v:
                d[ii][jj] = v
                nv = v+1 if not vacant[ii][jj] else v
                q.append((nv, ii, jj))
ans = 0
for v in p:
    v -= 1
    x,y = v//n, v%n
    ans += d[x][y]
#     print(v, d[x][y], d)
    sub(x,y)
    vacant[x][y] = True
print(ans)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [[None]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        d[i][j] = min(i, n-1-i, j, n-1-j)
vacant = [[False]*n for _ in range(n)]
def sub(x,y):
    v = d[x][y]
    q = [(v, x, y)]
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    while q:
        v,i,j = q.pop()
        for xx, yy in zip(dx,dy):
            ii = i+xx
            jj = j+yy
            if ii<0 or jj<0 or ii>=n or jj>=n:
                continue
            if d[ii][jj]>v:
                d[ii][jj] = v
                nv = v+1 if not vacant[ii][jj] else v
                q.append((nv, ii, jj))
ans = 0
for v in p:
    v -= 1
    x,y = v//n, v%n
    ans += d[x][y]
#     print(v, d[x][y], d)
    sub(x,y)
    vacant[x][y] = True
print(ans)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)