406381: GYM102392 I Absolute Game

Alice and Bob are playing a game. Alice has an array $$$a$$$ of $$$n$$$ integers, Bob has an array $$$b$$$ of $$$n$$$ integers. In each turn, a player removes one element of his array. Players take turns alternately. Alice goes first.

The game ends when both arrays contain exactly one element. Let $$$x$$$ be the last element in Alice's array and $$$y$$$ be the last element in Bob's array. Alice wants to maximize the absolute difference between $$$x$$$ and $$$y$$$ while Bob wants to minimize this value. Both players are playing optimally.

Find what will be the final value of the game.

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 1\,000$$$) — the number of values in each array.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers in Alice's array.

The third line contains $$$n$$$ space-separated integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the numbers in Bob's array.

Print the absolute difference between $$$x$$$ and $$$y$$$ if both players are playing optimally.

4
2 14 7 14
5 10 9 22

4

1
14
42

28

In the first example, the $$$x=14$$$ and $$$y=10$$$. Therefore, the difference between these two values is $$$4$$$.

In the second example, the size of the arrays is already $$$1$$$. Therefore, $$$x=14$$$ and $$$y=42$$$.