题目描述

一个电影院有 $N$ 排座位，每排有 $N$ 个座位，所有座位沿水平及垂直方向对齐。第一排第一座的编号为 $1$，第一排第二座编号为 $2$，第二排第一座的编号为 $N+1$，以此类推，第 $N$ 排第 $N$ 座的编号为 $N^2$。

一开始，每个座位上都有一名观众，之后观众陆续退场，其中第 $i$ 个退场的观众编号为 $P_i$。退场时，观众可以沿着上下左右四个方向移动，当他路过的座位还有人时，就要打一次招呼。当观众走到任意一条座位的边缘时，就算离开了。请计算，观众应该选择什么样的散场路线，才能使得打招呼的次数之和最小。

输入格式

• 第一行：一个整数表示 $N$；
• 第二行：$N\times N$ 个整数表示 $T_1,T_2,\dots,T_n$。

输出格式

• 输出结果。

3
1 3 7 9 5 4 8 6 2

1

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$
• $1\leq P_i\leq N^2$，且每个 $P_i$ 不相等