每年 SWERC 比赛时，$n^2$ 名参赛选手都会聚集在场馆外拍摄无人机照片。赛事社交媒体经理 Jennifer 将他们排列成一个 $n \times n$ 的正方形。她非常专业，知道第 $i$ 行第 $j$ 列的选手年龄为 $a_{i,j}$。巧合的是，她注意到没有两名选手的年龄相同，且所有人的年龄都在 $1$ 到 $n^2$ 之间。
Jennifer 计划让一些选手举起一面印有 ICPC 标志的横幅，使其与地面平行，以便在航拍照片中清晰可见。为了拍出完美的 SWERC 无人机照片，她将遵循以下步骤：
- 首先，Jennifer 将选择四名站在轴对齐矩形顶点的选手。
- 然后，她会让两名年龄较小的选手举起其中一根杆子，而两名年龄较大的选手举起另一根杆子。
- 最后，她将展开横幅，用两根杆子支撑其两端。显然，这只有在两根杆子平行且不交叉的情况下才能完成，如下图所示。
由于 Jennifer 非常优柔寡断，她想尝试所有可能的横幅排列方式，但她担心这会导致选手们错过比赛。请问有多少种不同的方式可以选择四名选手来举起杆子，从而拍出一张完美的照片？如果两种选择中至少有一名选手不同，则视为不同的选择。
输入格式
第一行包含一个整数 $n$ ($2 \le n \le 1500$)。 接下来的 $n$ 行描述了选手的年龄。具体来说，第 $i$ 行包含整数 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n^2$)。 保证当 $i \neq k$ 或 $j \neq l$ 时，$a_{i,j} \neq a_{k,l}$。
输出格式
输出 Jennifer 选择四名选手举起杆子的方案数。
样例
输入格式 1
2 1 3 4 2
输出格式 1
0
说明
共有 4 名选手，排列如下：
| 1 | 3 |
|---|---|
| 4 | 2 |
只有一种选择四名选手的方式，其中一根杆子由年龄为 1 和 2 的选手举起，另一根由年龄为 3 和 4 的选手举起。但正如我们在图中看到的，杆子交叉了。
由于没有有效的选择方式，答案为 0。
输入格式 2
2 3 2 4 1
输出格式 2
1
说明
4 名选手排列如下：
| 3 | 2 |
|---|---|
| 4 | 1 |
同样，只有一种选择四名选手的方式，但这次杆子没有交叉。
因此，答案为 1。
输入格式 3
3 9 2 4 1 5 3 7 8 6
输出格式 3
6
说明
9 名选手排列如下：
| 9 | 2 | 4 |
|---|---|---|
| 1 | 5 | 3 |
| 7 | 8 | 6 |
有 6 种选择四名选手的方式使得杆子不交叉，如下图所示。