Try our new interface for solving problems

John`s Inversions

John`s Inversions

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 contains one integer number n (1n100000) - the number of cards in the deck. The following n lines describe one card each. The i-th line contains two integer numbers ri and bi (1ri, bi109) - the numbers written on i-th card in red and blue colors respectively.


Print the minimal possible number of nice inversions.

Time limit 1 second
Memory limit 256 MiB
Input example #1
10 3
20 2
30 1
Output example #1
Input example #2
2 2
5 25
2 1
10 9
Output example #2