7493번 - Collisions 다국어

문제

Identical small balls are located on a straight line and can move along this line only. Each ball moves with a constant velocity, but velocities of different balls may be different. When two balls meet, a perfectly elastic collision occurs. It’s a common-known physical fact, that when two equal-mass physical bodies A and B collide perfectly elastically, they swap their velocities, i. e. new A’s velocity is old B’s one, and new B’s is old A’s.

Your task is to write a program to find the total number of collisions.

입력

The first line at input contains the number of balls N (3 ≤ N ≤ 200000). Each of the following N lines contains 2 space-separated integers — the starting coordinate and the velocity of corresponding ball. All start coordinates are in range –10¹¹< x< 10¹¹, all velocities are in range –10⁸< v< 10⁸. All start coordinates are different. It’s guaranteed that each collision involves exactly two balls (none involves three or more balls together).

출력

Your program should output exactly one integer number in a single line – the total number of collisions (or 987654321987654321 if the number is infinite).

제한

힌트