Problem K
Bazaar

In an epic but tiny pirate game, several players compete for resources in order to gain a large enough booty to bury at deserted islands. After pillaging resources from peaceful settlements, players need to visit the bazaar in order to exchange their goods for pieces o’ eight to add to their booty.

There are $2N$ different goods in the game, each of a different type such as coffee, silk and sugarcane. The bazaar has the following mechanism for setting the prices of each good. There is always exactly one good that is priced $i$ pieces o’ eight, for each positive integer $i$ such that $1 \le i \le 2N$. At the start of the game, the prices of the goods are arbitrarily assigned. Whenever a pirate sells a good priced $i$, its new price becomes $1$, and any good previously priced $j$ where $1 \le j < i$ has its price set to $j + 1$.

Two players are in the endgame phase of a match, and are now rapidly trying to sell off all their pillaged goods. At the moment, each player is in possession of exactly $N$ goods. A player can only exchange a single good per turn, after which the turn passes over to the other player. Given the current prices of the goods and what goods each player has, your task is to compute the difference between the amount of pieces o’ eight the players receive, if they are playing optimally. Optimal play means that if $A$ and $B$ are the numbers of pieces o’ eight the first and second player receives respectively, player $A$ tries to maximize $A - B$, while player $B$ tries to maximize $B - A$.

Input

The first line contains the even integer $2N$ ($1 \le 2N \le 100\, 000$), the number of types of goods in the game.

The next line contains $N$ space-separated integers $a_1, \dots , a_ N$ ($1 \le a_ i \le 2N$), the prices of the goods that the first player has. This is followed by a line of the same format containing the prices of goods that the second player has.

Output

Output a single integer: the number of pieces o’ eight the first player receives minus the number of pieces o’ eight the second player receives, if playing optimally as described in the statement.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.

Explanation of sample 3

At the start of the game, the goods of the first player are priced $1$ and $2$, and those of the second player are priced $3$ and $4$. One optimal strategy is for the first player to start by selling the good priced $2$, which increases the price of their remaining good to $2$. The second player can then sell the good priced $4$, increasing the price of the first player’s good to $3$ and the price of second player’s remaining good to $4$. The two players then sell their remaining good at prices $3$ and $4$.

The first player receives a total of $2 + 3 = 5$ pieces o’ eight, while the second one gets a total of $4 + 4 = 8$ pieces o’ eight, o the answer is $5 - 8 = -3$.

2
1
2

-1

2
2
1

0

4
1 2
3 4

-3