409781: GYM103741 K Triangles
Description
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.
InputThe 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$$$.
OutputOutput an integer representing the number of triangles.
ExamplesInput3 1 1 2 2 3 1Output
8Input
6 1 1 2 1 3 2 4 3 1 3 2 4Output
20Note
The figure below illustrates the first example.