Problem:
 Score : 700 points    Problem Statement Tonight, in your favourite cinema they are giving the movie Joker and all seats are occupied. In the cinema there are N rows with N seats each, forming an N\times N square. We denote with 1, 2,\dots, N the viewers in the first row (from left to right); with N+1, \dots, 2N the viewers in the second row (from left to right); and so on until the last row, whose viewers are denoted by N^2-N+1,\dots, N^2 .  At the end of the movie, the viewers go out of the cinema in a certain order: the i -th viewer leaving her seat is the one denoted by the number P_i . The viewer P_{i+1} waits until viewer P_i has left the cinema before leaving her seat.
To exit from the cinema, a viewer must move from seat to seat until she exits the square of seats (any side of the square is a valid exit). A viewer can move from a seat to one of its 4 adjacent seats (same row or same column).
While leaving the cinema, it might be that a certain viewer x goes through a seat currently occupied by viewer y ; in that case viewer y will hate viewer x forever. Each viewer chooses the way that minimizes the number of viewers that will hate her forever.  Compute the number of pairs of viewers (x, y) such that y will hate x forever.      Constraints  2 \le N \le 500  The sequence P_1, P_2, \dots, P_{N^2} is a permutation of \{1, 2, \dots, N^2\} .         Input The input is given from Standard Input in the format  N  P_1  P_2  \cdots  P_{N^2}       Output If ans is the number of pairs of viewers described in the statement, you should print on Standard Output  ans         Sample Input 1 3
1 3 7 9 5 4 8 6 2      Sample Output 1 1  Before the end of the movie, the viewers are arranged in the cinema as follows:  1 2 3
4 5 6
7 8 9  The first four viewers leaving the cinema ( 1 , 3 , 7 , 9 ) can leave the cinema without going through any seat, so they will not be hated by anybody.  Then, viewer 5 must go through one of the seats where viewers 2 , 4 , 6 , 8 are currently seated while leaving the cinema; hence he will be hated by at least one of those viewers.  Finally the remaining viewers can leave the cinema (in the order 4 , 8 , 6 , 2 ) without going through any occupied seat (actually, they can leave the cinema without going through any seat at all).       Sample Input 2 4
6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8      Sample Output 2 3       Sample Input 3 6
11 21 35 22 7 36 27 34 8 20 15 13 16 1 24 3 2 17 26 9 18 32 31 23 19 14 4 25 10 29 28 33 12 6 5 30      Sample Output 3 11

Solution (Python):
N=int(input())
plist=list(map(int,input().split()))

sit=[[1]*N for _ in range(N)]
dist=[[min(i,j,N-1-i,N-1-j) for j in range(N)] for i in range(N)]

answer=0
for p in plist:
  i=(p-1)//N
  j=(p-1)%N
  
  sit[i][j]=0
  answer+=dist[i][j]
  
  queue=[(i,j,dist[i][j])]
  d=0
  while queue:
    x,y,d=queue.pop()
    if x>0 and dist[x-1][y]>d:
      dist[x-1][y]=d
      queue.append((x-1,y,d+sit[x-1][y]))
    if x<N-1 and dist[x+1][y]>d:
      dist[x+1][y]=d
      queue.append((x+1,y,d+sit[x+1][y]))    
    if y>0 and dist[x][y-1]>d:
      dist[x][y-1]=d
      queue.append((x,y-1,d+sit[x][y-1]))
    if y<N-1 and dist[x][y+1]>d:
      dist[x][y+1]=d
      queue.append((x,y+1,d+sit[x][y+1]))
      
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
l = list(map(int,input().split()))
l = [((i-1)//n, (i-1) % n) for i in l]
check = [[1]*n for i in range(n)]
d =  [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]

ans = 0
for x,y in l:
    check[x][y] = 0
    ans += d[x][y]
    q = [(x,y,d[x][y])]
    while q:
        bx,by,z = q.pop()

        if bx != 0:
            if d[bx-1][by] > z:
                d[bx-1][by] = z
                q.append((bx-1,by,z+check[bx-1][by]))
        if bx != n-1:
            if d[bx+1][by] > z:
                d[bx+1][by] = z
                q.append((bx+1,by,z+check[bx+1][by]))
        if by != 0:
            if d[bx][by-1] > z:
                d[bx][by-1] = z
                q.append((bx,by-1,z+check[bx][by-1]))
        if by != n-1:
            if d[bx][by+1] > z:
                d[bx][by+1] = z
                q.append((bx,by+1,z+check[bx][by+1]))  
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    l = [((i-1)//n, (i-1) % n) for i in l]
    check = [[1]*n for i in range(n)]
    d =  [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]

    ans = 0
    for x,y in l:
        check[x][y] = 0
        ans += d[x][y]
        q = [(x,y,d[x][y])]
        while q:
            bx,by,z = q.pop()

            if bx != 0:
                if d[bx-1][by] > z:
                    d[bx-1][by] = z
                    q.append((bx-1,by,z+check[bx-1][by]))
            if bx != n-1:
                if d[bx+1][by] > z:
                    d[bx+1][by] = z
                    q.append((bx+1,by,z+check[bx+1][by]))
            if by != 0:
                if d[bx][by-1] > z:
                    d[bx][by-1] = z
                    q.append((bx,by-1,z+check[bx][by-1]))
            if by != n-1:
                if d[bx][by+1] > z:
                    d[bx][by+1] = z
                    q.append((bx,by+1,z+check[bx][by+1]))  
    print(ans)
if __name__ =="__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    l = [((i-1)//n, (i-1) % n) for i in l]
    check = [[1 for j in range(n)] for i in range(n)]
    d =  [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]

    ans = 0
    for x,y in l:
        check[x][y] = 0
        ans += d[x][y]
        q = []
        q.append((x,y,d[x][y]))
        while q:
            bx,by,z = q.pop()

            if bx != 0:
                if d[bx-1][by] > z:
                    d[bx-1][by] = z
                    q.append((bx-1,by,z+check[bx-1][by]))
            if bx != n-1:
                if d[bx+1][by] > z:
                    d[bx+1][by] = z
                    q.append((bx+1,by,z+check[bx+1][by]))
            if by != 0:
                if d[bx][by-1] > z:
                    d[bx][by-1] = z
                    q.append((bx,by-1,z+check[bx][by-1]))
            if by != n-1:
                if d[bx][by+1] > z:
                    d[bx][by+1] = z
                    q.append((bx,by+1,z+check[bx][by+1]))  
    print(ans)
if __name__ =="__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[1 for j in range(n)] for i in range(n)]
    d =  [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]

    ans = 0
    for t in l:
        t -=1
        x = t//n
        y = t%n
        check[x][y] = 0
        ans += d[x][y]
        q = []
        q.append((x,y,d[x][y]))
        while q:
            bx,by,z = q.pop()

            if bx != 0:
                if d[bx-1][by] > z:
                    d[bx-1][by] = z
                    q.append((bx-1,by,z+check[bx-1][by]))
            if bx != n-1:
                if d[bx+1][by] > z:
                    d[bx+1][by] = z
                    q.append((bx+1,by,z+check[bx+1][by]))
            if by != 0:
                if d[bx][by-1] > z:
                    d[bx][by-1] = z
                    q.append((bx,by-1,z+check[bx][by-1]))
            if by != n-1:
                if d[bx][by+1] > z:
                    d[bx][by+1] = z
                    q.append((bx,by+1,z+check[bx][by+1]))  
    print(ans)
if __name__ =="__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[True]*n for i in range(n)]
    d =  [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]

    ans = 0
    for t in l:
        t -=1
        x = t//n
        y = t%n
        check[x][y] = False
        ans += d[x][y]
        q = []
        q.append([x,y,d[x][y]])
        while q:
            bx,by,z = q.pop()

            if bx != 0:
                if d[bx-1][by] > z:
                    d[bx-1][by] = z
                    q.append([bx-1,by,z+check[bx-1][by]])
            if bx != n-1:
                if d[bx+1][by] > z:
                    d[bx+1][by] = z
                    q.append([bx+1,by,z+check[bx+1][by]])
            if by != 0:
                if d[bx][by-1] > z:
                    d[bx][by-1] = z
                    q.append([bx,by-1,z+check[bx][by-1]])
            if by != n-1:
                if d[bx][by+1] > z:
                    d[bx][by+1] = z
                    q.append([bx,by+1,z+check[bx][by+1]])  
    print(ans)
if __name__ =="__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[True]*n for i in range(n)]
    d =  [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]

    ans = 0
    for t in l:
        t -=1
        x = t//n
        y = t%n
        check[x][y] = False
        ans += d[x][y]
        q = []
        q.append((x,y,d[x][y]))
        while q:
            bx,by,z = q.pop()

            if bx != 0:
                if d[bx-1][by] > z:
                    d[bx-1][by] = z
                    q.append((bx-1,by,z+check[bx-1][by]))
            if bx != n-1:
                if d[bx+1][by] > z:
                    d[bx+1][by] = z
                    q.append((bx+1,by,z+check[bx+1][by]))
            if by != 0:
                if d[bx][by-1] > z:
                    d[bx][by-1] = z
                    q.append((bx,by-1,z+check[bx][by-1]))
            if by != n-1:
                if d[bx][by+1] > z:
                    d[bx][by+1] = z
                    q.append((bx,by+1,z+check[bx][by+1]))  
    print(ans)
if __name__ =="__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[1]*n for i in range(n)]
    d =  [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]

    ans = 0
    for t in l:
        t -=1
        x = t//n
        y = t%n
        check[x][y] = 0
        ans += d[x][y]
        q = []
        q.append((x,y,d[x][y]))
        while q:
            bx,by,z = q.pop()

            if bx != 0:
                if d[bx-1][by] > z:
                    d[bx-1][by] = z
                    q.append((bx-1,by,z+check[bx-1][by]))
            if bx != n-1:
                if d[bx+1][by] > z:
                    d[bx+1][by] = z
                    q.append((bx+1,by,z+check[bx+1][by]))
            if by != 0:
                if d[bx][by-1] > z:
                    d[bx][by-1] = z
                    q.append((bx,by-1,z+check[bx][by-1]))
            if by != n-1:
                if d[bx][by+1] > z:
                    d[bx][by+1] = z
                    q.append((bx,by+1,z+check[bx][by+1]))  
    print(ans)
if __name__ =="__main__":
    main()

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[1]*n for i in range(n)]
    d =  [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]
    
    ans = 0
    for t in l:
        t -=1
        x = t//n
        y = t%n
        check[x][y] = 0
        ans += d[x][y]
        q = deque([])
        q.append((x,y,d[x][y]))
        while q:
            bx,by,z = q.popleft()

            if bx != 0:
                if d[bx-1][by] > z:
                    d[bx-1][by] = z
                    q.append((bx-1,by,z+check[bx-1][by]))
            if bx != n-1:
                if d[bx+1][by] > z:
                    d[bx+1][by] = z
                    q.append((bx+1,by,z+check[bx+1][by]))
            if by != 0:
                if d[bx][by-1] > z:
                    d[bx][by-1] = z
                    q.append((bx,by-1,z+check[bx][by-1]))
            if by != n-1:
                if d[bx][by+1] > z:
                    d[bx][by+1] = z
                    q.append((bx,by+1,z+check[bx][by+1]))  
    print(ans)
if __name__ =="__main__":
    main()

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[1]*n for i in range(n)]
    d = [[float("INF")]*n for i in range(n)]

    for i in range((n+1)//2):
        for j in range(i,n-i):
            d[i][j] = i
            d[-1-i][j] = i
        for j in range(i,n-i):
            d[j][i] = i
            d[j][-1-i] = i
    def solve(l):
        ans = 0
        for t in l:
            t -=1
            x = t//n
            y = t%n
            check[x][y] = 0
            ans += d[x][y]
            q = deque([])
            q.append((x,y,d[x][y]))
            while q:
                bx,by,z = q.popleft()

                if bx != 0:
                    if d[bx-1][by] > z:
                        d[bx-1][by] = z
                        q.append((bx-1,by,z+check[bx-1][by]))
                if bx != n-1:
                    if d[bx+1][by] > z:
                        d[bx+1][by] = z
                        q.append((bx+1,by,z+check[bx+1][by]))
                if by != 0:
                    if d[bx][by-1] > z:
                        d[bx][by-1] = z
                        q.append((bx,by-1,z+check[bx][by-1]))
                if by != n-1:
                    if d[bx][by+1] > z:
                        d[bx][by+1] = z
                        q.append((bx,by+1,z+check[bx][by+1]))  
        return ans

    
    print(solve(l))

if __name__ =="__main__":
    main()

Solution (Python):

import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N = ir()
    P = lr()
    P = [((p-1)//N, (p-1)%N) for p in P]
    dp = [[min(i, N-1-i, j, N-1-j) for j in range(N)] for i in range(N)]
    people = [[True] * N for i in range(N)]

    answer = 0
    for i, j in P:
        answer += dp[i][j]
        people[i][j] = False
        que = deque([(i, j, dp[i][j])])
        popleft = que.popleft; append = que.append
        while que:
            y, x, cur = popleft()
            cur += people[y][x]
            if x > 0:
                if dp[y][x-1] > cur:
                    dp[y][x-1] = cur
                    append((y, x-1, cur))
            if x < N-1:
                if dp[y][x+1] > cur:
                    dp[y][x+1] = cur
                    append((y, x+1, cur))
            if y > 0:
                if dp[y-1][x] > cur:
                    dp[y-1][x] = cur
                    append((y-1, x, cur))
            if y < N-1:
                if dp[y+1][x] > cur:
                    dp[y+1][x] = cur
                    append((y+1, x, cur))

    print(answer)
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n = int(input())
Ps = list(map(int, input().split()))
Ps = [p-1 for p in Ps]
fs = [0] * (n**2)


for x in range(n**2):
    i,j = divmod(x,n)
    x = min(i,n-1-i)
    y = min(j,n-1-j)
    fs[i*n+j] = min(x,y)

ans = 0
mvs = [1, -1, n, -n]
occupied = [1] * (n**2)
for p in Ps:
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: 
        p_ = q.popleft()
        dist = fs[p_]
        for mv in mvs:
            if 0 <= p_+mv < n**2:
                p_next = p_ + mv
                
                
                
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]

print(ans)

Solution (Python):
def main():
    n=int(input())
    Num=[0]*(n**2+1)
    Exited=[0]*(n**2+1)
    X=tuple(map(int,input().split()))
    for i in range(n**2):
        q,r=divmod(i,n)
        Num[i+1]=min(q,n-q-1,r,n-r-1)
    ans=0
    for x in X:
        ans+=Num[x]
        Exited[x]=1
        Stack=[x]
        while Stack:
            v=Stack.pop()
            if v>n and (Num[v]<Num[v-n] and (Exited[v] or Num[v-n]-Num[v]>1)):
                Num[v-n]-=1
                Stack.append(v-n)
            if v<=n**2-n and (Num[v]<Num[v+n] and (Exited[v] or Num[v+n]-Num[v]>1)):
                Num[v+n]-=1
                Stack.append(v+n)
            if v%n!=0 and (Num[v]<Num[v+1] and (Exited[v] or Num[v+1]-Num[v]>1)):
                Num[v+1]-=1
                Stack.append(v+1)
            if v%n!=1 and (Num[v]<Num[v-1] and (Exited[v] or Num[v-1]-Num[v]>1)):
                Num[v-1]-=1
                Stack.append(v-1)
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):

import sys
buff_readline = sys.stdin.buffer.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def slv(N, P):
    M = N+2
    cost = [0] * M**2
    occupy = [1] * M**2
    for i in range(N):
        im = i*M + M + 1
        for j in range(N):
            cost[im+j] = min(i, j, N-i-1, N-j-1)

    ds = [-1, 1, -M, M]
    ans = 0
    for p in P:
        p -= 1
        x = p // N
        y = p % N
        p = x * M + y + M + 1
        ans += cost[p]
        occupy[p] = 0
        s = []
        s.append(p)
        while s:
            pi = s.pop()
            for d in ds:
                ni = pi + d
                nc = cost[pi] + occupy[pi]
                if nc < cost[ni]:
                    cost[ni] = nc
                    s.append(ni)
    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))


if __name__ == '__main__':
    main()

Solution (Python):
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]







        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)

Solution (Python):
n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        if 0 <= x+1 < n and 0 <= y < n and seat[x+1][y] > seat[x][y] + reserved[x][y]:
            seat[x+1][y] = seat[x][y] + reserved[x][y]
            q.append((x+1, y))
        if 0 <= x-1 < n and 0 <= y < n and seat[x-1][y] > seat[x][y] + reserved[x][y]:
            seat[x-1][y] = seat[x][y] + reserved[x][y]
            q.append((x-1, y))
        if 0 <= x < n and 0 <= y+1 < n and seat[x][y+1] > seat[x][y] + reserved[x][y]:
            seat[x][y+1] = seat[x][y] + reserved[x][y]
            q.append((x, y+1))
        if 0 <= x < n and 0 <= y-1 < n and seat[x][y-1] > seat[x][y] + reserved[x][y]:
            seat[x][y-1] = seat[x][y] + reserved[x][y]
            q.append((x, y-1))


print(ans)

Solution (Python):
from collections import deque
import sys
imput = sys.stdin.readline


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

cost = [0] * (n * n)
for i in range(n):
    for j in range(n):
        cost[i * n + j] = min(i, j, n - i - 1, n - j - 1)

occ = [True] * (n * n)
ans = 0
for start in p:
    start -= 1
    q = deque([start])
    ans += cost[start]
    occ[start] = False
    while q:
        ij = q.popleft()
        i, j = divmod(ij, n)

        nxt_ij = (i + 1) * n + j
        if not(0 <= i + 1 < n and 0 <= j < n):
             pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)
              
        nxt_ij = (i - 1) * n + j
        if not(0 <= i - 1 < n and 0 <= j < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)

        nxt_ij = i * n + (j + 1)
        if not(0 <= i + 0 < n and 0 <= j + 1 < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)

        nxt_ij = i * n + (j - 1)
        if not(0 <= i < n and 0 <= j - 1 < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import deque

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

def nears(n):
    ret = []
    if n%N != 0:
        ret.append(n-1)
    if n%N != N-1:
        ret.append(n+1)
    if n//N != 0:
        ret.append(n-N)
    if n//N != N-1:
        ret.append(n+N)
    return ret

NeedS = []
for p in range(N**2):
    NeedS.append(min([p%N, p//N, N-1-p%N, N-1-p//N]))

isChecked = [False]*(N**2)
ans = 0
for p in P:
    p -= 1
    ans += NeedS[p]
    isChecked[p] = True
    q = deque()
    q.append(p)
    while q:
        p = q.popleft()
        d = NeedS[p]
        if not isChecked[p]: d += 1
        for np in nears(p):
            if d < NeedS[np]:
                NeedS[np] = d
                q.append(np)
print(ans)

Solution (Python):
import sys


def solve(n, ppp):
    n2 = n + 2
    nsq = n2 * n2
    seats = [0] * nsq
    is_seated = [0] * nsq
    for i in range(n):
        ud = min(i, n - 1 - i)
        ri = (i + 1) * n2
        for j in range(n):
            ij = ri + j + 1
            seats[ij] = min(ud, j, n - 1 - j)
            is_seated[ij] = 1

    MOVES = [-n2, -1, 1, n2]

    ans = 0

    for p in ppp:
        i, j = divmod(p - 1, n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = 0

        q = []
        for di in MOVES:
            ni = i + di
            if seats[ni] > res:
                seats[ni] = res
                q.append(ni)

        while q:
            j = q.pop()
            val = seats[j]

            if is_seated[j]:
                val += 1
            for dj in MOVES:
                nj = j + dj
                if seats[nj] > val:
                    seats[nj] = val
                    q.append(nj)

    return ans


n, *ppp = map(int, sys.stdin.buffer.read().split())

print(solve(n, ppp))

Solution (Python):
import sys
import numpy as np
from numba import njit


def input(): return sys.stdin.readline().rstrip()


@njit
def solve(N, P):
    W = N + 2
    dp = np.zeros((W, W), np.int32)
    for _ in range(4):
        dp = dp.T[::-1]
        for n in range(1, (N + 1) // 2 + 1):
            dp[n, n:-n] = n
    filled = np.zeros_like(dp)
    filled[1:-1, 1:-1] = 1
    dp = dp.ravel()
    filled = filled.ravel()
    stack = np.empty_like(dp)
    ans = 0
    for n in P:
        n -= 1
        h, w = divmod(n, N)
        v = (h + 1) * W + (w + 1)
        ans += dp[v] - 1
        filled[v] = 0
        k = min(dp[v - 1], dp[v + 1], dp[v - W], dp[v + W])
        if dp[v] == k:
            return ans
        p = 0
        stack[0] = v
        dp[v] = k
        while p >= 0:
            v = stack[p]
            p -= 1
            for dx in (-1, 1, -W, W):
                w = v + dx
                k = dp[v] + filled[w]
                if dp[w] > k:
                    dp[w] = k
                    p += 1
                    stack[p] = w
    return ans


N = int(input())
P = np.array(input().split(), np.int32)

print(solve(N, P))

Solution (Python):
import sys
import numpy as np

from numba import njit


@njit
def solve(n, ppp):
    n2 = n + 2
    nsq = n2 * n2
    seats = np.zeros(nsq, dtype=np.int16)
    is_seated = np.zeros(nsq, dtype=np.int8)
    for i in range(n):
        ud = min(i, n - 1 - i)
        ri = (i + 1) * n2
        for j in range(n):
            ij = ri + j + 1
            seats[ij] = min(ud, j, n - 1 - j)
            is_seated[ij] = 1

    MOVES = np.array([-n2, -1, 1, n2], dtype=np.int32)

    ans = 0

    for pi in range(n * n):
        i, j = divmod(ppp[pi], n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = 0

        q = []
        for mi in range(4):
            ni = i + MOVES[mi]
            if seats[ni] > res:
                seats[ni] = res
                q.append(ni)

        while q:
            j = q.pop()
            
            val = seats[j]

            if is_seated[j]:
                val += 1
            for mi in range(4):
                nj = j + MOVES[mi]
                if seats[nj] > val:
                    seats[nj] = val
                    q.append(nj)

        
        
        

    return ans


n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int32) - 1






print(solve(n, ppp))

Solution (Python):
import sys
import numpy as np

from numba import njit


@njit('i4(i4,i4[:])', cache=True)
def solve(n, ppp):
    n2 = n + 2
    nsq = n2 * n2
    seats = np.zeros(nsq, dtype=np.int16)
    is_seated = np.zeros(nsq, dtype=np.int8)
    for i in range(n):
        ud = min(i, n - 1 - i)
        ri = (i + 1) * n2
        for j in range(n):
            ij = ri + j + 1
            seats[ij] = min(ud, j, n - 1 - j)
            is_seated[ij] = 1

    MOVES = np.array([-n2, -1, 1, n2], dtype=np.int32)

    ans = 0

    for pi in range(n * n):
        i, j = divmod(ppp[pi], n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = 0

        q = []
        for mi in range(4):
            ni = i + MOVES[mi]
            if seats[ni] > res:
                seats[ni] = res
                q.append(ni)

        while q:
            j = q.pop()
            
            val = seats[j]

            if is_seated[j]:
                val += 1
            for mi in range(4):
                nj = j + MOVES[mi]
                if seats[nj] > val:
                    seats[nj] = val
                    q.append(nj)

        
        
        

    return ans


n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int32) - 1






print(solve(n, ppp))

Solution (Python):
N, = map(int, input().split())
R = [0] * (N**2+1)
V = [0] * (N**2+1)
X = list(map(int, input().split()))
for ai in range(N**2):
    i, j = divmod(ai, N)
    R[ai+1] = min([i, N-i-1, j, N-j-1])
r = 0
for a in X:
    r += R[a]
    V[a] = 1
    stack=[a]
    while stack:
        v = stack.pop()
        if v>N and (R[v]<R[v-N] and (V[v] or R[v]+1<R[v-N])):
            R[v-N] -= 1
            stack.append(v-N)
        if v<N**2+1-N and (R[v]<R[v+N] and (V[v] or R[v]+1<R[v+N])):
            R[v+N] -= 1
            stack.append(v+N)
        if v%N and (R[v]<R[v+1] and (V[v] or R[v]+1<R[v+1])):
            R[v+1] -= 1
            stack.append(v+1)
        if v%N-1 and (R[v]<R[v-1] and (V[v] or R[v]+1<R[v-1])):
            R[v-1] -= 1
            stack.append(v-1)
print(r)

Solution (Python):
N, = map(int, input().split())
R = [0] * (N**2+1)
V = [0] * (N**2+1)
X = list(map(int, input().split()))
for ai in range(N**2):
    i, j = divmod(ai, N)
    R[ai+1] = min([i, N-i-1, j, N-j-1])

r = 0
for a in X:
    r += R[a]
    V[a] = 1
    stack=[a]
    while stack:
        v = stack.pop()
        if v>N:
            if not(R[v]>=R[v-N] or ((1-V[v]) and R[v]+1 >= R[v-N])):
                R[v-N] -= 1
                stack.append(v-N)
        if v<N**2+1-N:
            if not(R[v]>=R[v+N] or ((1-V[v]) and R[v]+1 >= R[v+N])):
                R[v+N] -= 1
                stack.append(v+N)
        if v%N:
            if not(R[v]>=R[v+1] or ((1-V[v]) and R[v]+1 >= R[v+1])):
                R[v+1] -= 1
                stack.append(v+1)
        if v%N!=1:
            if not(R[v]>=R[v-1] or ((1-V[v]) and R[v]+1 >= R[v-1])):
                R[v-1] -= 1
                stack.append(v-1)
print(r)

Solution (Python):
N, = map(int, input().split())
R = [0] * (N**2+1)
V = [0] * (N**2+1)
X = list(map(int, input().split()))
for ai in range(N**2):
    i, j = divmod(ai, N)
    R[ai+1] = min([i, N-i-1, j, N-j-1])

r = 0
for a in X:
    r += R[a]
    V[a] = 1
    stack=[a]
    while stack:
        v = stack.pop()
        ccs = []
        if v>N:
            ccs.append(v-N)
        if v<N**2+1-N:
            ccs.append(v+N)
        if v%N:
            ccs.append(v+1)
        if v%N!=1:
            ccs.append(v-1)
        for u in ccs:
            if R[v]>=R[u] or ((1-V[v]) and R[v]+1 >= R[u]):
                continue
            R[u] -= 1
            stack.append(u)
print(r)