RECTANGL - Rectangles

You are given a set S of N points in the plane and must count the number of distinct axis-parallel rectangles whose four vertices all lie in S (that is, count those rectangles which have two sides parallel to the x-axis, and the other two sides parallel to the y-axis).

Input

The first line of the input is N (1 ≤ N ≤ 250000), the number of points in S. N lines then follow, where the i-th line is of the form "xi yi", giving the coordinates of a point (xi, yi) in S. All given points are distinct, and all coordinates fit into a 32-bit signed integer.

Output

Your output should consist of a single number, the number of distinct axis-parallel rectangles whose four vertices all lie in S, followed by a newline.

Example

Input:
6
-1 0
-1 1
0 0
0 1
1 0
1 1

Output:
3

Added by:Minilek
Date:2007-10-25
Time limit:1s-4.273s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT Individual Contest 2007

hide comments
2020-05-15 16:54:29 Renzo
Is the TL too strict?
My O(sqrt(N)*N) solution using unordered_map<long long, int> is giving time limit exceed. While using a hash table made by hand is giving AC.

Last edit: 2020-05-15 16:54:51
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.