题目描述

电影《Joker》今晚即将上映，你常去的剧场已经座无虚席。该剧场有 $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$ 的观众离开后再行动。离开剧场时，观众需要不断从一个座位移动到相邻的座位，最终走出这个正方形区域（可以从四条边的任意一处离开）。每次移动时，只能向前后左右四个方向移动。

如果编号为 $x$ 的观众在离开剧场时，经过了编号为 $y$ 的观众尚未离开时所坐的座位，那么编号为 $x$ 的观众将被编号为 $y$ 的观众永远讨厌。每位观众会选择一种移动方式，使得讨厌自己的人数最少。

请计算所有会被讨厌的观众对 $(x, y)$ 的有序对的总数。

输入格式

输入从标准输入读入，格式如下：

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

输出格式

输出一个整数 $ans$，表示所有会被讨厌的观众对 $(x, y)$ 的总数。

$ans$

样例 1

输入

3
1 3 7 9 5 4 8 6 2

输出

1

样例 2

输入

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

输出

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

输出

11

说明/提示

限制

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

样例解释 1

放映结束前，剧场内观众的分布如下：

1 2 3
4 5 6
7 8 9

最先离开的 $4$ 人（编号 $1$、$3$、$7$、$9$）可以不经过他人座位直接离开，因此不会被任何人讨厌。之后，编号为 $5$ 的观众在离开时，必须经过编号为 $2$、$4$、$6$、$8$ 中至少一个人的座位，因此他至少会被上述观众中的一人讨厌。最后剩下的 $4$ 人（依次为 $4$、$8$、$6$、$2$）无需经过他人座位即可离开（甚至无需移动）。

由 ChatGPT 4.1 翻译