题目内容

给定一个$N*N$的二维矩阵，其中包含$[1，N^2]$的互不相同的正整数。

定义一种操作:

每次可以选择矩阵中的一个元素，将其与其在顺时针螺旋顺序中的下一个元素交换位置

例如: 在$3*3$的矩阵中,

螺旋顺序为从左上角$[0,0]$开始，向右到$[0,2]$，向下到$[2,2]$，向左到$[2,0]$，再向上到$[1,0]$，最 后到中心$[1,1]$。

目标是通过若干次操作，将矩阵变为“顺时针螺旋递增”顺序，即螺旋遍历时元素依次为 $1,2,3,...,N^2$。

求将给定矩阵转换为顺时针螺旋递增顺序所需的最小操作次数。

输入描述

第一行为整数$N$;

接下来$N$行，每行$N$个整数,表示矩阵。

参数范围:

矩阵的N取值范围为$[1,10^3]$；

矩阵中元素的取值范围$[1,N^2]$；

输出描述

一个整数; 表示最小操作次数。

特别注意:

结果可能过大，因此结果需要取模$1000000007$。

例如，计算初始结果为:$1000000008$，请返回$1$。

样例1

输入

2
3 1
2 4

输出

3

说明

根据要求，通过若干次操作得到的目标矩阵为：

$1\ 2$

$4\ 3$

第一次交换,选择$(0,0)$的$3$与螺旋顺序上相邻的$(0,1)$的$1$交换，矩阵为:

$1\ 3$

$2\ 4$

第二次交换,选择$(1,1)$的$4$与螺旋顺序上相邻的$(1,0)$的$2$交换，矩阵为:

$1\ 3$

$4\ 2$

第三次交换，选择$(0,1)$的$3$与螺旋顺序上相邻的$(1,1)$的$2$交换，矩阵为：

$1\ 2$

$4\ 3$

目标达成;

操作次数$3$;

样例2

输入

3
3 2 1
6 5 4
9 8 7

输出

10

说明

解释:根据要求，通过若干次操作得到的目标矩阵为:

$1\ 2\ 3$

$8\ 9\ 4$

$7\ 6\ 5$

开始交换(注意选择螺旋顺序上相邻的交换);

第$1$次交换:

$3\ 2\ 1$

$5\ 6\ 4$

$9\ 8\ 7$

第$2$次交换: $3\ 2\ 1$

$9\ 6\ 4$

$5\ 8\ 7$

第$3$次交换: $3\ 2\ 1$

$6\ 9\ 4$

$5\ 8\ 7$

第$4$次交换:

$3\ 2\ 1$

$6\ 9\ 4$

$8\ 5\ 7$

第$5$次交换:

$3\ 2\ 1$

$8\ 9\ 4$

$6\ 5\ 7$

第$6$次交换:

$3\ 2\ 1$

$8\ 9\ 4$

$6\ 7\ 5$

第$7$次交换:

$3\ 2\ 1$

$8\ 9\ 4$

$7\ 6\ 5$

第$8$次交换:

$3\ 1\ 2$

$8\ 9\ 4$

$7\ 6\ 5$

第$9$次交换:

$1\ 3\ 2$

$8\ 9\ 4$

$7\ 6\ 5$

第$10$次交换:

$1\ 2\ 3$

$8\ 9\ 4$

$7\ 6\ 5$

目标达成;

操作次数$10$;