John's Inversions

Time limit3sMemory limit256 MB

Summary

Order cards with two attached numbers to minimize the total count of same-color inversions summed over red and blue sequences.

Level: Medium6 of 10
Topics: Sorting, Greedy, Divide and conquer
Solved: No attempts yet

Problem

John recently learned the definition of an inversion.

An inversion in a sequence of numbers $s_1, s_2, \dots$ is any pair of indices $i < j$ such that $s_i > s_j$ .

John believes inversions are a great way to measure how well a sequence is sorted: the fewer inversions a sequence has, the better it is sorted. For example, a sequence sorted in ascending order has zero inversions.

Peter gave John a stack of $n$ cards. Each card has two numbers written on it — one in red and one in blue. John lays the cards out in a row in any order he likes. Reading the cards from left to right yields two sequences: the sequence of red numbers and the sequence of blue numbers.

John calls an inversion nice if the two numbers forming it have the same color. In other words, the number of nice inversions equals the number of inversions in the red sequence plus the number of inversions in the blue sequence. John wants to arrange the cards so that the total number of nice inversions is as small as possible.

Find the minimum possible number of nice inversions.

Input

The first line contains a single integer $n$ — the number of cards ( $1 \le n \le 100\,000$ ).

Each of the next $n$ lines contains two integers $r_i$ and $b_i$ ( $1 \le r_i, b_i \le 10^9$ ) — the numbers written in red and in blue on the $i$ -th card, respectively.

Output

Print a single integer — the minimum possible number of nice inversions.

Examples2

Example 1
Input
```
3
10 3
20 2
30 1
```
Expected output
```
3
```
Example 2
Input
```
4
2 2
5 25
2 1
10 9
```
Expected output
```
1
```