Drone Photo

Today, as 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. She knows that the contestant at the intersection of row $i$ and column $j$ is $a_{i,j}$ years old. She also notices that no two contestants have the same age, and every age is between $1$ and $n^2$.

Jennifer wants some contestants to hold a banner with the ICPC logo, parallel to the ground, so that it is clearly visible from the air. She follows these steps to take the perfect SWERC drone photo.

• First, she selects four contestants standing at the vertices of an axis-aligned rectangle.
• Then the two younger contestants hold one pole, and the two older contestants hold the other.
• Finally, she unfolds the banner and uses the poles to support its two ends. This works only if the two poles are parallel and do not cross (see the pictures below).

Jennifer would like to try every possible arrangement, but she worries this will make the contestants late for the competition. How many different ways are there to choose the four contestants holding the poles so that the photo is perfect? Two choices are different if at least one contestant is in one but not the other.

The first line contains an integer $n$ ($2 \le n \le 1500$). The next $n$ lines describe the ages. The $i$-th line contains the integers $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n^2$). It is guaranteed that $a_{i,j} \ne a_{k,l}$ whenever $i \ne k$ or $j \ne l$.

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