螺旋矩阵排序

题目描述

Y 同学得到了一个 $N \times N$ 的二维矩阵，其中包含了从 $1$ 到 $N^2$ 的所有正整数，且每个数恰好出现一次。

我们定义一种顺时针螺旋顺序来遍历该矩阵：从左上角 $(0,0)$ 出发，首先向右移动到 $(0, N-1)$ ，然后向下到 $(N-1, N-1)$ ，再向左到 $(N-1, 0)$ ，接着向上到 $(1, 0)$ ，然后继续向右……如此循环，不断向内螺旋，直到遍历完所有 $N^2$ 个位置。

Y 同学可以对矩阵执行一种操作：选择矩阵中的任意一个元素，并将其与它在螺旋顺序中的下一个元素交换位置。

他的目标是通过若干次操作，将矩阵变为一个“螺旋递增”矩阵。一个矩阵是螺旋递增的，当且仅当沿着螺旋顺序遍历矩阵时，得到的元素序列恰好是 $1, 2, 3, \dots, N^2$ 。

请你计算，将给定的初始矩阵转变为目标状态，所需的最小操作次数是多少。

输入格式

第一行输入一个正整数 $N$ ，表示矩阵的维度。

接下来 $N$ 行，每行输入 $N$ 个整数，描述这个 $N \times N$ 的矩阵。

输出格式

输出一个整数，表示所需的最小操作次数。由于结果可能很大，请将答案对 $10^9+7$ 取模。

样例

样例输入 #1

2
3 1
2 4

样例输出 #1

样例输入 #2

样例输出 #2

提示

样例 1 解释

对于 $2 \times 2$ 矩阵，螺旋顺序为 $(0,0) \to (0,1) \to (1,1) \to (1,0)$ 。

初始矩阵为 [[3, 1], [2, 4]]。
按螺旋顺序展开，得到序列 $A = \{3, 1, 4, 2\}$ 。
目标矩阵为 [[1, 2], [4, 3]]。
按螺旋顺序展开，目标序列为 $B = \{1, 2, 3, 4\}$ 。

问题转化为：将序列 $A$ 通过相邻元素交换的方式变为序列 $B$ 所需的最小次数。这等价于计算序列 $A$ 的逆序对数量。 $A = \{3, 1, 4, 2\}$ 中的逆序对有：

$(3, 1)$
$(3, 2)$
$(4, 2)$ 共 3 对，因此最小操作次数为 3。

数据范围与约定

对于 $100\%$ 的数据，保证：

$1 \le N \le 1000$
矩阵中的元素是 $1$ 到 $N^2$ 的一个排列。
最终答案需要对 $10^9 + 7$ 取模。