ACM ICPC 2011–2012, NEERC 2011
John has recently come across the definition of an inversion.
An inversion in a sequence of numbers sk is any pair si, sj such that i < j and si > sj.
John believes that inversions are a perfect tool for estimation of how well a sequence of numbers is sorted. The smaller the number of inversions in the sequence, the better it is sorted. For example, the sequences sorted in the ascending order have zero inversions in them.
Peter gave John a stack of n cards. Each card has two numbers written on it - one in red and one in blue color. John is anxious to apply his knowledge of inversions to that stack.
He places the cards in front of him in arbitrary order and calculates the total number of nice inversions in front of him. John considers an inversion to be nice if it consists of the numbers of the same color. In our case nice inversion can be formed by either two blue or two red numbers. If the number of nice inversions is too big by John's standards, he rearranges the cards and repeats the process.
Your task is to help John find out the minimal possible number of nice inversions he can get while following his algorithm.
The first line of the input file contains one integer number n - the number of cards in the deck (1 ≤ n ≤ 100000). The following n lines describe one card each. The i-th line contains two integer numbers ri and bi (1 ≤ ri, bi ≤ 109) - the numbers written on i-th card in red and blue colors respectively.
Print the minimal possible number of nice inversions.
3 10 3 20 2 30 1
4 2 2 5 25 2 1 10 9