Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

rev_p = [0] * (n * n)
for offset in range(len(p)):
    rev_p[p[offset] - 1] = offset

costs = [0] * (n * n)

for i in range(n*n):
    costs[i] = min(i // n, n - i // n - 1, i % n, n - i % n - 1)

removed = set()

ans = 0
for i, pi in enumerate(p):
    ans += costs[pi-1]
    removed.add(pi-1)

    d = deque()
    d.append((pi-1, costs[pi-1]))

    while d:
        pos, cost = d.popleft()

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n * n:
                next_cost = cost if pos in removed else cost + 1

                if costs[pos+offset] > next_cost:
                    costs[pos+offset] = next_cost
                    d.append((pos+offset, next_cost))

print(ans)


Fixed submission:
from collections import deque

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

costs = [0] * n2

for i in range(n2):
    costs[i] = min(i // n, n - i // n - 1, i % n, n - i % n - 1)

remains = [1] * n2

ans = 0
for i, pi in enumerate(p):
    ans += costs[pi-1]
    remains[pi-1] = 0

    d = deque()
    d.append((pi-1, costs[pi-1]))

    while d:
        pos, cost = d.popleft()

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n2:
                next_cost = cost + remains[pos]

                if costs[pos+offset] > next_cost:
                    costs[pos+offset] = next_cost
                    d.append((pos+offset, next_cost))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

rev_p = [0] * (n * n)
for offset in range(len(p)):
    rev_p[p[offset] - 1] = offset

ans = 0
for i, pi in enumerate(p):
    d = deque()
    d.append((0, pi-1))
    memo = set()

    while d:
        cost, pos = d.popleft()

        if pos < n or pos >= n * (n-1) or pos % n == 0 or pos % n == n-1:
            ans += cost
            break

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n * n:
                if pos + offset not in memo:
                    memo.add(pos + offset)

                    if rev_p[pos + offset] < i:
                        d.appendleft((cost, pos + offset))
                    else:
                        d.append((cost + 1, pos + offset))

print(ans)


Fixed submission:
from collections import deque

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

costs = [0] * n2

for i in range(n2):
    costs[i] = min(i // n, n - i // n - 1, i % n, n - i % n - 1)

remains = [1] * n2

ans = 0
for i, pi in enumerate(p):
    ans += costs[pi-1]
    remains[pi-1] = 0

    d = deque()
    d.append((pi-1, costs[pi-1]))

    while d:
        pos, cost = d.popleft()

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n2:
                next_cost = cost + remains[pos]

                if costs[pos+offset] > next_cost:
                    costs[pos+offset] = next_cost
                    d.append((pos+offset, next_cost))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

rev_p = [0] * (n * n)
for offset in range(len(p)):
    rev_p[p[offset] - 1] = offset

ans = 0
for i, pi in enumerate(p):
    d = deque()
    d.append((0, pi-1))
    memo = set()

    while d:
        cost, pos = d.popleft()

        if pos in memo:
            continue

        memo.add(pos)

        if pos < n or pos >= n * (n-1) or pos % n == 0 or pos % n == n-1:
            ans += cost
            break

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n * n:
                if rev_p[pos + offset] < i:
                    d.appendleft((cost, pos + offset))
                else:
                    if pos+offset not in memo:
                        d.append((cost + 1, pos + offset))

print(ans)


Fixed submission:
from collections import deque

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

costs = [0] * n2

for i in range(n2):
    costs[i] = min(i // n, n - i // n - 1, i % n, n - i % n - 1)

remains = [1] * n2

ans = 0
for i, pi in enumerate(p):
    ans += costs[pi-1]
    remains[pi-1] = 0

    d = deque()
    d.append((pi-1, costs[pi-1]))

    while d:
        pos, cost = d.popleft()

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n2:
                next_cost = cost + remains[pos]

                if costs[pos+offset] > next_cost:
                    costs[pos+offset] = next_cost
                    d.append((pos+offset, next_cost))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop

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

rev_p = [0] * (n * n)
for offset in range(len(p)):
    rev_p[p[offset] - 1] = offset

ans = 0
for i, pi in enumerate(p):
    h = []
    heappush(h, (0, pi-1))
    memo = set()

    while h:
        cost, pos = heappop(h)

        if pos in memo:
            continue

        memo.add(pos)

        if pos < n or pos >= n * (n-1) or pos % n == 0 or pos % n == n-1:
            ans += cost
            break

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n * n:
                if rev_p[pos + offset] < i:
                    heappush(h, (cost, pos + offset))
                else:
                    heappush(h, (cost + 1, pos + offset))

print(ans)


Fixed submission:
from collections import deque

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

costs = [0] * n2

for i in range(n2):
    costs[i] = min(i // n, n - i // n - 1, i % n, n - i % n - 1)

remains = [1] * n2

ans = 0
for i, pi in enumerate(p):
    ans += costs[pi-1]
    remains[pi-1] = 0

    d = deque()
    d.append((pi-1, costs[pi-1]))

    while d:
        pos, cost = d.popleft()

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n2:
                next_cost = cost + remains[pos]

                if costs[pos+offset] > next_cost:
                    costs[pos+offset] = next_cost
                    d.append((pos+offset, next_cost))

print(ans)