PAIRSORT - Double Sorting

Here we describe a typical problem. There are n balls and n boxes. Each ball is labeled by a unique number from 1 to n. Initially each box contains one of these balls. We can swap two balls in adjacent boxes. We are to sort these balls in increasing order by swaps, i.e. move the ball labeled by 1 to the first box, labeled by 2 to the second box, and so forth. The question is how many swaps are needed.

Now let us consider the situation where the balls are doubled, that is, there are 2n balls and n boxes, exactly two balls are labeled by k for each 1 ≤ kn, and the boxes contain two balls each. We can swap two balls in adjacent boxes, one ball from each box. We are to move the both balls labeled by 1 to the first box, labeled by 2 to the second box, and so forth. The question is again how many swaps are needed.

Here is one interesting fact. We need 10 swaps to sort [5; 4; 3; 2; 1] (the state with 5 in the first box, 4 in the second box, and so forth): swapping 5 and 4, then 5 and 3, 5 and 2, 5 and 1, 4 and 3, 4 and 2, 4 and 1, 3 and 2, 3 and 1,and finally 2 and 1. Then how many swaps we need to sort [5, 5; 4, 4; 3, 3; 2, 2; 1, 1] (the state with two 5’s in the first box, two 4’s in the second box, and so forth)? Some of you might think 20 swaps — this is not true, but the actual number is 15.

Write a program that calculates the number of swaps for the two-ball version and verify the above fact.

Input

The input has the following format:

       n
       ball1,1 ball1,2
       ball2,1 ball2,2
       ...
       balln,1 balln,2

n is the number of boxes (1 ≤ n ≤ 8). balli,1 and balli,2 , for 1 ≤ in, are the labels of two balls initially contained by the i-th box.

Output

Print the minimum possible number of swaps.

Example

Input:
5
5 5
4 4
3 3
2 2
1 1

Output:
15

Added by:Bin Jin
Date:2009-11-03
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 CPP
Resource:JAG Summer Camp 2009, day2

hide comments
2013-11-12 21:20:24 Shreyans
Can anyone please provide the explanation for the given test case in question?
2013-06-25 10:30:29 Trilok Sharma
Please provide more test cases ....

the answers to the following test cases:
8
87654321
87654321
ANS:42

7
7654321
7654321
ANS: 31
2013-06-07 13:59:41 Pushkar Mishra
Please provide more test cases.
2013-06-07 03:56:55 Pushkar Mishra
the answers to the following test cases:
8
87654321
87654321
ANS:42

7
7654321
7654321
ANS: 32

Cheers
2013-03-10 15:52:54 _maverick
please someone who has solved this kindly give the value for
8 and 7
87654321 7654321
87654321 7654321
is it 42 and 33 :0
i am working on this thing for more than 2 days can some one help me.
thanks in advance.
2011-07-31 20:24:19 om
i am getting wrong answer ..
give some more test cases ..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.