Queue Reordering

Problem Description

During a PE class, $n$ students line up in a queue. From front to back, the $i$-th student has height $h_i$ and weight $w_i$. The current lineup looks uneven, and the teacher wants the students to stand in order of decreasing height, and among students of the same height, in order of decreasing weight. When rearranging the queue, only two adjacent students may be swapped at a time. The teacher wants to know the minimum number of swaps needed to arrange the queue into the target order.

Input Format

The first line contains a positive integer $n$, the number of students.

The following $n$ lines each contain two positive integers $h_i$ and $w_i$, the height and weight of the $i$-th student.

Output Format

Output one line containing one integer: the minimum number of swaps needed.

Sample Input 1

5
1 60
3 70
2 80
4 55
4 50

Sample Input 2

5
4 0
4 0
2 0
3 0
1 0

Sample Output 1

8

Sample Output 2

1

Sample Explanation

For the first sample, the target order is: the student of height $4$ and weight $55$ stands first, then the student of height $4$ and weight $50$, then height $3$ weight $70$, then height $2$ weight $80$, and finally height $1$ weight $60$. Replace each student in the initial queue by his position index in the target queue; the initial sequence becomes $[4, 2, 3, 0, 1]$. The minimum number of adjacent swaps to sort this sequence equals the number of inversions in it. The sequence $[4, 2, 3, 0, 1]$ has inversions: $4$ forms $4$ pairs with the following $2, 3, 0, 1$; $2$ forms $2$ pairs with $0, 1$; $3$ forms $2$ pairs with $0, 1$; for a total of $8$. Therefore at least $8$ swaps are needed.

Constraints

For all test cases, $1 \le n \le 3000$ and $0 \le h_i, w_i \le 10^9$ are guaranteed.