Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys

input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

from collections import deque

def main():
    N = INT()
    P = LI()
    adjlist = [[1,1,1,1] for i in range(N**2)]

    def isGoal(node):
        return node//N == 0 or node//N == N-1 or node%N == N-1 or node%N == 0

    output = 0

    for p in P:
        min_cost = 10**9
        queue = deque([(p-1,0)])
        cost_mat = [N]*N**2

        while queue:
            node,cost = queue.popleft()
            if isGoal(node):
                min_cost = cost
                break
            
            if cost >= min_cost or cost_mat[node] <= cost:
                continue

            cost_mat[node] = cost
                        
            for direction in range(4):
                if adjlist[node][direction] == 0:
                    if direction == 0:
                        queue.appendleft((node-N,cost))
                    elif direction == 1:
                        queue.appendleft((node+N,cost))
                    elif direction == 2:
                        queue.appendleft((node-1,cost))
                    else:
                        queue.appendleft((node+1,cost))
                else:
                    if direction == 0:
                        queue.append((node-N,cost+1))
                    elif direction == 1:
                        queue.append((node+N,cost+1))
                    elif direction == 2:
                        queue.append((node-1,cost+1))
                    else:
                        queue.append((node+1,cost+1))
        
        node = p-1
        if node//N > 0:
            adjlist[node-N][1] = 0
        if node//N < N-1:
            adjlist[node+N][0] = 0
        if node%N > 0:
            adjlist[node-1][3] = 0
        if node%N < N-1:
            adjlist[node+1][2] = 0
        
        output += min_cost


    print(output)


if __name__ == '__main__':
    main()

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    n = INT()
    P = LI()
    cost = [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]
    issit = [[True for _ in range(n)] for _ in range(n)]
    ans = 0

    for p in P:
        i,j = divmod(p-1,n)
        issit[i][j] = False
        ans += cost[i][j]

        q = [(i, j, cost[i][j])]
        while q:
            n_i, n_j, cur_cost = q.pop()

            if n_i > 0 and cost[n_i-1][n_j] > cur_cost:
                cost[n_i-1][n_j] = cur_cost
                q.append((n_i-1,n_j,cur_cost+issit[n_i-1][n_j]))

            if n_i < n-1 and cost[n_i+1][n_j] > cur_cost:
                cost[n_i+1][n_j] = cur_cost
                q.append((n_i+1,n_j,cur_cost+issit[n_i+1][n_j]))

            if n_j > 0 and cost[n_i][n_j-1] > cur_cost:
                cost[n_i][n_j-1] = cur_cost
                q.append((n_i,n_j-1,cur_cost+issit[n_i][n_j-1]))
 
            if n_j < n-1 and cost[n_i][n_j+1] > cur_cost:
                cost[n_i][n_j+1] = cur_cost
                q.append((n_i,n_j+1,cur_cost+issit[n_i][n_j+1]))
    print(ans)

if __name__ == '__main__':
    main()