CF1662N Drone Photo

今天，和往年一样，$n^2$ 名参赛者聚集在 SWERC 会场外，准备拍摄一张无人机合影。活动的社交媒体经理 Jennifer 将他们排成了一个 $n\times n$ 的正方形。Jennifer 工作非常出色，她知道站在第 $i$ 行第 $j$ 列交点的参赛者年龄为 $a_{i,j}$ 岁。巧合的是，她注意到没有两位参赛者年龄相同，并且所有人的年龄都在 $1$ 到 $n^2$ 岁之间。 Jennifer 计划让几位参赛者举起一条印有 ICPC 标志的横幅，并使其与地面平行，这样在航拍照片中能够清晰可见。她将按照以下步骤拍摄完美的 SWERC 无人机合影： - 首先，Jennifer 会选择站在某个轴对齐矩形四个顶点上的四位参赛者。 - 然后，她会让年龄较小的两位参赛者举起一根横幅杆，年龄较大的两位参赛者举起另一根横幅杆。 - 最后，她会展开横幅，用两根杆子支撑横幅的两端。显然，只有当两根杆子平行且不交叉时，才能这样做，如下图所示。  Jennifer 很犹豫，想尝试所有可能的横幅摆放方式，但她担心这样会让参赛者们迟到。请问 Jennifer 有多少种不同的方式选择四位参赛者举起横幅杆，从而拍摄出完美的照片？如果至少有一位参赛者不同，则两种选择被认为是不同的。

第一行包含一个整数 $n$（$2\le n \le 1500$）。 接下来的 $n$ 行描述了参赛者的年龄。具体来说，第 $i$ 行包含整数 $a_{i,1},a_{i,2},\ldots,a_{i,n}$（$1\le a_{i,j}\le n^2$）。 保证 $a_{i,j}\neq a_{k,l}$，当 $i\neq k$ 或 $j\neq l$ 时成立。

输出 Jennifer 选择四位参赛者举起横幅杆的方案数。

在第一个样例中，有 $4$ 位参赛者，排列如下：  只有一种方式选择四位参赛者，即年龄为 $1$ 和 $2$ 的参赛者举一根杆，年龄为 $3$ 和 $4$ 的参赛者举另一根杆。但如图所示，两根杆交叉了。  因此，没有合法的选择方式，答案为 $0$。 在第二个样例中，$4$ 位参赛者排列如下：  同样只有一种方式选择四位参赛者，但这次两根杆没有交叉。  因此，答案为 $1$。 在第三个样例中，$9$ 位参赛者排列如下：  有 $6$ 种方式选择四位参赛者，使得两根杆不交叉，如下图所示。  由 ChatGPT 4.1 翻译