问题描述

在一个体育场馆内，有一块 $n$ 行 $n$ 列的座位方阵，每个位置都坐了恰好一个观众。

这 $n^2$ 个观众编号分别为 $1,2,...,n^2$，其中坐在第 $i$ 行第 $j$ 列的观众编号为 $(i-1)*n+j$。

由于人数太多，所以观众们的离场有一个确定的顺序 $p_1,p_2,...,p_{n^2}$。从 $p_1$ 号观众开始，每次在第 $p_i$ 个观众离场后，$p_{i+1}$ 号观众才开始离场。

观众只能从某个座位移动到相邻行列上下左右的四个座位中的某一个，直到移动到座位方阵之外（方阵的任何一侧都可以离开）。

但每当一个观众移动到了一个还坐着人的位置，就会造成 $1$ 的不便度（因为要起身让他过去，不过这个座位的人并不会移动），每个观众都会选择所有离开方阵的移动方案中造成的不便度之和最小的那个移动方案。

现在主办方想知道对于给定的离场顺序，所有观众造成的不便度之和为多少。

输入描述

第一行一个正整数 $n$ ，表示方阵的行列个数。

接下来一行 $n^2$ 个数，分别表示 $p_1,p_2,...,p_{n^2}$。

输出描述

输出一行一个整数，表示所有观众的不便度之和。

3
1 3 5 7 9 2 4 6 8

1

样例解释 1

初始方阵:

1 2 3

4 5 6

7 8 9

除了 $5$ 号观众都可以直接离开，而 $5$ 号观众离开时周围 $2,4,6,8$ 四个观众都还没离开，所以造成 $1$ 不便度到方阵边上，然后离开。

数据范围和说明

对于 30% 的数据, $n\le 10$。

对于 70% 的数据，$n\le 50$。

对于 100% 的数据，$1\le n\le 200$。

保证 $p_1,p_2,...,p_{n^2}$ 是 $[1,n^2]$ 的排列。

大样例

大样例下载