Description

Alice and Bob are playing a game. Alice has a sequence $a$ containing $n$ integers, and Bob has a sequence $b$ containing $n$ integers. In each round, the player must delete one number from their own sequence. The players take turns, and Alice moves first.

When both sequences have only one number left, the game ends. Let the remaining number in Alice’s sequence be $x$, and the remaining number in Bob’s sequence be $y$. Alice wants to maximize the absolute value of the difference between $x$ and $y$, while Bob wants to minimize this value. Both players play optimally.

Compute the result when the game ends.

Input Format

The first line contains an integer $n \ (1 \leq n \leq 1 \ 000)$, representing the number of integers in each sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n \ (1 \leq a_i \leq 10^9)$, representing the numbers in Alice’s sequence.

The third line contains $n$ integers $b_1, b_2, \dots, b_n \ (1 \leq b_i \leq 10^9)$, representing the numbers in Bob’s sequence.

Output Format

Output the absolute value of the difference between $x$ and $y$ when both players play optimally.

4
2 14 7 14
5 10 9 22

4

1
14
42

28

Hint

In the first sample, $x=14$ and $y=10$, so the difference between the two numbers is $4$.

In the second sample, both sequences already have only one number left, so $x=14$ and $y=42$.

Translated by ChatGPT 5