CF1662N.Drone Photo

Today, like every year at SWERC, the $n^2$ contestants have gathered outside the venue to take a drone photo. Jennifer, the social media manager for the event, has arranged them into an $n\times n$ square. Being very good at her job, she knows that the contestant standing on the intersection of the $i$-th row with the $j$-th column is $a_{i,j}$ years old. Coincidentally, she notices that no two contestants have the same age, and that everyone is between $1$ and $n^2$ years old.

Jennifer is planning to have some contestants hold a banner with the ICPC logo parallel to the ground, so that it is clearly visible in the aerial picture. Here are the steps that she is going to follow in order to take the perfect SWERC drone photo.

• First of all, Jennifer is going to select four contestants standing on the vertices of an axis-aligned rectangle.
• Then, she will have the two younger contestants hold one of the poles, while the two older contestants will hold the other pole.
• Finally, she will unfold the banner, using the poles to support its two ends. Obviously, this can only be done if the two poles are parallel and do not cross, as shown in the pictures below.

Being very indecisive, Jennifer would like to try out all possible arrangements for the banner, but she is worried that this may cause the contestants to be late for the competition. How many different ways are there to choose the four contestants holding the poles in order to take a perfect photo? Two choices are considered different if at least one contestant is included in one but not the other.

今天，和每年 SWERC 比赛一样，$n^2$ 名参赛者聚集在赛场外拍摄无人机照片。本次活动的社交媒体经理詹妮弗（Jennifer）已将他们排成一个 $n \times n$ 的方阵。她非常专业，清楚地知道站在第 $i$ 行第 $j$ 列位置上的参赛者年龄为 $a_{i,j}$ 岁。巧合的是，她注意到所有参赛者的年龄互不相同，且每个人的年龄均在 $1$ 到 $n^2$ 岁之间（含端点）。

詹妮弗计划安排若干参赛者手持印有 ICPC 标志的横幅，并使其保持与地面平行，以便在航拍照片中清晰可见。为拍出完美的 SWERC 无人机照片，她将按以下步骤操作：

• 首先，詹妮弗将选出四名站在某个轴对齐矩形四个顶点上的参赛者；
• 接着，让其中年龄较小的两名参赛者共同持握一根杆子，而年龄较大的两名参赛者则共同持握另一根杆子；
• 最后，展开横幅，用这两根杆子分别支撑横幅的两端。显然，这仅当两根杆子彼此平行且不相交时才可行，如下图所示：

由于詹妮弗十分优柔寡断，她希望尝试所有可能的横幅布置方式；但她又担心这会导致参赛者错过比赛。那么，有多少种不同的方式来选出这四名持杆参赛者，从而拍出一张完美的照片？若两种选择中至少有一名参赛者被选入其中一种而未被选入另一种，则认为这两种选择不同。

The first line contains a single integer $n$ ($2\le n \le 1500$).

The next $n$ lines describe the ages of the contestants. Specifically, the $i$-th line contains the integers $a_{i,1},a_{i,2},\ldots,a_{i,n}$ ($1\le a_{i,j}\le n^2$).

It is guaranteed that $a_{i,j}\neq a_{k,l}$ if $i\neq k$ or $j\neq l$.

第一行包含一个整数 $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$）。

保证当 $i\neq k$ 或 $j\neq l$ 时，有 $a_{i,j}\neq a_{k,l}$。

Print the number of ways for Jennifer to choose the four contestants holding the poles.

输出珍妮弗选择握持杆子的四位参赛者的方案数。

In the first sample, there are $4$ contestants, arranged as follows.

There is only one way to choose four contestants, with one pole held by contestants aged $1$ and $2$ and the other one by contestants aged $3$ and $4$. But then, as we can see in the picture, the poles cross.

Since there is no valid way to choose four contestants, the answer is $0$.

In the second sample, the $4$ contestants are arranged as follows.

Once again, there is only one way to choose four contestants, but this time the poles don't cross.

Therefore, the answer is $1$.

In the third sample, the $9$ contestants are arranged as follows.

There are $6$ ways of choosing four contestants so that the poles don't cross, as shown in the following pictures.

在第一个样例中，共有 $4$ 名参赛者，排列方式如下：

仅有一种方式选出四名参赛者：一根杆由年龄为 $1$ 和 $2$ 的参赛者持握，另一根杆由年龄为 $3$ 和 $4$ 的参赛者持握。但如图所示，这两根杆相交。

由于不存在一种合法方式选出四名参赛者使得杆不相交，因此答案为 $0$。

在第二个样例中，$4$ 名参赛者的排列方式如下：

同样地，仅有一种方式选出四名参赛者，但此时两根杆不相交。

因此，答案为 $1$。

在第三个样例中，$9$ 名参赛者的排列方式如下：

共有 $6$ 种选出四名参赛者的方式，使得所持杆不相交，如下图所示：