Absolute Game#11282
Alice and Bob are playing a game. Alice has an array of integers, Bob has an array of 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 be the last element in Alice's array and be the last element in Bob's array. Alice wants to maximize the absolute difference between and 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 (1 \le n \le 1000) - the number of values in each array.
The second line contains 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 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 and if both players are playing optimally.
Example 1
Example 2
In the first example, the x = 14 and y = 10. Therefore, the difference between these two values is .
In the second example, the size of the arrays is already . Therefore, x = 14 and y = 42.