Collisions

Time limit1sMemory limit128 MB

Summary

Identical balls on a line move at constant velocities and swap velocities on elastic collision; count total collisions, or report infinity if unbounded.

Level: Medium7 of 10
Topics: Sorting, Math, Array, Implementation
Solved: No attempts yet

Problem

Identical small balls sit on a straight line and can move only along that line. Each ball moves at a constant velocity, but different balls may have different velocities. When two balls meet, a perfectly elastic collision occurs. It is a well-known physical fact that when two bodies of equal mass A and B collide perfectly elastically, they exchange velocities: after the collision A moves with B's previous velocity and B moves with A's previous velocity.

Write a program that computes the total number of collisions.

Input

The first line contains the number of balls N ( $3 \le N \le 200000$ ).

Each of the next N lines contains two space-separated integers: the starting coordinate and the velocity of one ball. All starting coordinates satisfy $-10^{11} < x < 10^{11}$ and all velocities satisfy $-10^{8} < v < 10^{8}$ . All starting coordinates are distinct. It is guaranteed that every collision involves exactly two balls (no collision involves three or more balls at the same instant).

Output

Print a single integer on one line: the total number of collisions. If the number of collisions were infinite, print 987654321987654321 instead.

Examples3

Example 1
Input
```
3
-5 3
0 -1
7 -2
```
Expected output
```
3
```
Example 2
Input
```
4
0 -3
1 -1
2 2
3 5
```
Expected output
```
0
```
Example 3
Input
```
4
0 10
1 7
2 3
3 -5
```
Expected output
```
6
```