今天,就像每年在 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},\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}$$$。
输出
打印 Jennifer 选择四名拿着杆的参赛者的方法数。
示例
输入 #1
2 1 3 4 2
输出 #1
0
输入 #2
2 3 2 4 1
输出 #2
1
输入 #3
3 9 2 4 1 5 3 7 8 6
输出 #3
6
注意
在第一个样本中,有 $$$4$$$ 参赛者,排列如下。
选择四名参赛者的方式只有一种,其中一杆由$$$1$$$和$$$2$$$年龄的参赛者持有,另一杆由$$$3$$$和$$$4$$$年龄的参赛者持有。但随后,正如我们在图中看到的,两极交叉了。
由于没有有效的方法来选择四名参赛者,所以答案是 $$$0$$$。
在第二个样本中,$$$4$$$ 参赛者的排列如下。
再次,选择四名参赛者的方法只有一种,但这次两极不交叉。
因此,答案是$$$1$$$。
在第三个样本中,$$$9$$$ 参赛者的排列如下。
有$$$6$$$选择四名参赛者的方法,使两极不交叉,如下图所示。