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^11 < x < 10^11, all velocities are in range –10^8 < v < 10^8. 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).