#![allow(non_snake_case)]
use proconio::{input};
fn main() {
input! {
N: usize,
P: [usize; N * N]
}
use std::collections::{VecDeque};
let mut dist = vec![vec![-1; N]; N];
let mut queue = VecDeque::new();
for i in 0..N {
for j in 0..N {
if i == 0 || j == 0 || i == N - 1 || j == N - 1 {
dist[i][j] = 1;
queue.push_back((i as i32, j as i32));
}
}
}
while let Some((y, x)) = queue.pop_front() {
for (dy, dx) in &[(1, 0), (0, 1), (-1, 0), (0, -1)] {
let ny = y + dy;
let nx = x + dx;
if ny < 0 || nx < 0 || ny >= N as i32 || nx >= N as i32 { continue }
if dist[ny as usize][nx as usize] == -1 {
dist[ny as usize][nx as usize] = dist[y as usize][x as usize] + 1;
queue.push_back((ny, nx));
}
}
}
let mut ans = 0;
let mut grid = vec![vec![true; N]; N];
for p in P {
let y = ((p - 1) / N) as i32;
let x = ((p - 1) % N) as i32;
grid[y as usize][x as usize] = false;
dist[y as usize][x as usize] -= 1;
ans += dist[y as usize][x as usize] as i64;
let mut queue = VecDeque::new();
queue.push_back((y, x));
while let Some((y, x)) = queue.pop_front() {
for (dy, dx) in &[(1, 0), (0, 1), (-1, 0), (0, -1)] {
let ny = y + dy;
let nx = x + dx;
if ny < 0 || nx < 0 || ny >= N as i32 || nx >= N as i32 { continue }
let cost = if grid[ny as usize][nx as usize] { 1 } else { 0 };
if dist[ny as usize][nx as usize] > dist[y as usize][x as usize] + cost {
dist[ny as usize][nx as usize] = dist[y as usize][x as usize] + cost;
queue.push_back((ny, nx))
}
}
}
}
println!("{}", ans);
}