409781: GYM103741 K Triangles

Walk_alone has a $$$500\times 500$$$ square grid in a plane. The lower-left corner of the grid locates at $$$(0,0)$$$, and all squares in it are of size $$$1\times 1$$$.

There are $$$n$$$ segments in the grid, the $$$i$$$-th of which connecting point $$$(x_i,y_i)$$$ and $$$(x_i-1,y_i-1)$$$. Now you are required to find out the number of triangles in the grid.

The first line contains an integer $$$n\ (1\le n\le 250\,000)$$$, the number of segments in the grid.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i\ (1\le x_i,y_i\le 500)$$$ as described above. It is guaranteed that $$$(x_i,y_i)\neq (x_j,y_j)$$$ for all $$$i\neq j$$$.

Output an integer representing the number of triangles.

3
1 1
2 2
3 1

8

6
1 1
2 1
3 2
4 3
1 3
2 4

20

The figure below illustrates the first example.