Submit | All submissions | Best solutions | Back to list |

## 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 "*x _{i}*

*y*", giving the coordinates of a point (

_{i}*x*,

_{i}*y*) in

_{i}*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 1Output:3

Added by: | Minilek |

Date: | 2007-10-25 |

Time limit: | 0.114s-4.273s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |

Resource: | MIT Individual Contest 2007 |