In JOI village, there is a vast patch of unused land on which N scarecrows stand. Several times a year, the residents of JOI village hold a festival in the barren land, surrounded by the scarecrows. The village chief received a prophecy from the scarecrows and is obliged to build a field on the wastelands to facilitate the festival. In accordance to the prophecy, the village chief has declared that the field must satisfy these conditions:
- The boundaries of the field are straight lines parallel to the north-south direction or the east-west direction. The field is a rectangle.
- There are two scarecrows, one at the southwest corner and the other at the northeast corner.
- There are no other scarecrows within the field.
Of course, you are not allowed to move the precious scarecrows. Given the positions of the N scarecrows, how many ways can a field be built in accordance with the prophecy?
Read from standard input.
- On the first line, there is one integer N. This means that there are N scarecrows in the wastelands.
- On the ith line of the next N lines, there are two integers, Xi and Yi. This means that the ith scarecrow is at (Xi, Yi) on the xy plane representing the wastelands. East is in the direction of the positive x-axis and north is in the direction of the positive y-axis.
Print one line containing one integer to standard output, representing the number of ways the field can be built in accordance with the prophecy.
All test cases satisfy the following constraints:
- 1 ≤ N ≤ 200 000.
- 0 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N).
- 0 ≤ Yi ≤ 1 000 000 000 (1 ≤ i ≤ N).
- Xi (1 ≤ i ≤ N) are all mutually distinct.
- Yi (1 ≤ i ≤ N) are all mutually distinct.
Subtask 1 (5 points):
Subtask 2 (10 points):
Subtask 3 (85 points):
No further constraints.
Sample Input 1
Sample Output 1
In this example, there are three ways to build a prophecy-fulfilling field.
- The rectangle with (0, 0) as the southwest corner and (2, 2) as the northeast corner.
- The rectangle with (2, 2) as the southwest corner and (3, 4) as the northeast corner.
- The rectangle with (2, 2) as the southwest corner and (4, 3) as the northeast corner.
Sample Input 2
Sample Output 2
In this example, the scarecrows' positions are as follows: