题目描述

今晚，在你最喜欢的电影院放映《小丑》，所有座位都已经被占满。电影院里有 $N$ 行，每行有 $N$ 个座位，形成一个 $N\\times N$ 的方阵。我们用 $1, 2,\\dots, N$ 来表示第一行的观众（从左到右）；用 $N+1, \\dots, 2N$ 来表示第二行的观众（从左到右）；依此类推，直到最后一行，最后一行的观众用 $N^2-N+1,\\dots, N^2$ 表示。

电影结束后，观众以某种顺序离开电影院：第 $i$ 个离开座位的观众是编号为 $P_i$ 的观众。观众 $P_{i+1}$ 在观众 $P_i$ 离开影院之前等待，然后再离开座位。为了离开电影院，观众必须从一个座位移动到另一个座位，直到离开座位区域（方阵的任意边界都是有效的出口）。一个观众可以从一个座位移动到其相邻的 $4$ 个座位中的一个（同一行或同一列）。在离开电影院的过程中，可能会出现某个观众 $x$ 经过当前被观众 $y$ 占据的座位；在这种情况下，观众 $y$ 将永远憎恨观众 $x$。每个观众选择一种方式，使得憎恨她的观众数量最小。

计算观众对 $(x, y)$ 的组合数，其中观众 $y$ 将永远憎恨观众 $x$。

约束条件

• $2 \\le N \\le 500$
• 序列 $P_1, P_2, \\dots, P_{N^2}$ 是 $\\{1, 2, \\dots, N^2\\}$ 的一个排列。

输入

输入以以下格式从标准输入中给出：

$N$

$P_1$ $P_2$ $\\cdots$ $P_{N^2}$

输出

假设 $ans$ 是题目描述中描述的观众对数，你需要将其打印到标准输出中：

$ans$

示例输入 1

3
1 3 7 9 5 4 8 6 2

示例输出 1

1

在电影结束之前，电影院里的观众按照以下方式排列：

1 2 3
4 5 6
7 8 9

前四个离开电影院的观众（$1$, $3$, $7$, $9$）可以在不经过任何座位的情况下离开电影院，因此不会被任何人憎恨。

然后，观众 $5$ 在离开电影院时必须经过观众 $2$, $4$, $6$, $8$ 中的一个座位；因此，他将受到其中至少一个观众的憎恨。

最后，剩下的观众可以不经过任何被占据的座位（事实上，他们可以根本不经过任何座位）离开电影院（按照顺序为 $4$, $8$, $6$, $2$）。

示例输入 2

4
6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8

示例输出 2

3

示例输入 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

示例输出 3

11