John's Inversions#2379
John has recently come across the definition of an inversion.
An inversion in a sequence of numbers s_k is any pair s_i,\ s_j such that i < j and s_i > s_j.
John believes that inversions are a perfect tool for estimating how well a sequence of numbers is sorted. The fewer the inversions in the sequence, the better it is sorted. For example, if a sequence is sorted in ascending order, then it has zero inversions.
Petr gave John a deck of cards. Each card has two numbers written on it: one in red and one in blue. John wants to use this deck to apply his knowledge about inversions.
He arranges the cards in front of him in arbitrary order and calculates the total number of nice inversions in the resulting sequences of numbers. John considers an inversion to be nice if it consists of numbers of the same color. In this case, a nice inversion can be formed by either two blue or two red numbers. If the number of nice inversions is too large by John's standards, he shuffles the cards and repeats the process.
Your task is to help John find the minimal possible number of nice inversions he can get according to the described procedure.
The first line contains an integer (1 \leq n \leq 100000) — the number of cards in the deck. Each of the next lines describes one card. The -th line contains two integers r_i and b_i (1 \leq r_i, b_i \leq 10^9), the numbers written on the -th card in red and blue, respectively.
Print the minimal possible number of nice inversions.
Example 1
Example 2