Rectangular Plaza

Count axis-aligned rectangles whose corners include two given lamps and whose interior contains no other lamp, given all X and Y coordinates are distinct.

Hard8GeometrySortingDynamic programmingNo attempts yetTime limit1sMemory limit512 MB

Problem

Retangolândia is a very old city, so it keeps a lot of historical heritage. The city was planned many decades ago with every street running north to south or east to west. A renovation project is under way, and one part of it is a new rectangular plaza. The city government will pick the final site, but right now it wants to know how many sites are possible. The plaza has to line up with the streets, so on a map its four sides are horizontal and vertical segments. Keeping the historical heritage together with the new project takes a few conditions.

Street lamps built in the 19th century are scattered around the city. They have historical value, so no lamp may be taken down. Because of wear and missing maintenance, no street has more than one lamp left. When the plaza is placed, no lamp may lie in its interior. The landscape plan, on the other hand, requires two of the historical lamps to lie at two of the plaza's corners. The figure below shows an example with four lamps and the three possible sites for the plaza.

The city government hired a surveying company to record the position of every lamp. From that data, count how many different sites the plaza can take. The count sets the size of the team that will evaluate each site.

Input

The first line contains an integer NN, the number of lamps (1N30001 \le N \le 3000). Each of the next NN lines contains two integers XX and YY, the coordinates of one lamp (108X,Y108-10^8 \le X, Y \le 10^8). No street has two lamps left, so any two lamps differ in their XX coordinate and also differ in their YY coordinate.

Output

Print one line with the number of different possible sites for the plaza.