Абсолютна гра#11282
Аліса та Боб грають у гру. У Аліси є масив з цілих чисел, у Боба є масив з цілих чисел. Кожного ходу гравець видаляє один елемент зі свого масиву. Гравці ходять по черзі, починає Аліса.
Гра завершується, коли в обох масивах залишається рівно один елемент. Нехай буде останнім елементом масиву Аліси, а — останнім елементом масиву Боба. Аліса прагне максимізувати абсолютну різницю між і , тоді як Боб намагається мінімізувати цю різницю. Обидва гравці діють оптимально.
Визначте, якою буде остаточна вартість гри.
Перший рядок містить ціле число (1 \le n \le 1000) — кількість елементів у кожному масиві.
Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — елементи масиву Аліси.
Третій рядок містить цілих чисел b_1, b_2, \ldots, b_n (1 \le b_i \le 10^9) — елементи масиву Боба.
Виведіть абсолютну різницю між і , якщо обидва гравці грають оптимально.
Приклад 1
Приклад 2
У першому прикладі x = 14 і y = 10. Тому різниця між цими двома значеннями дорівнює .
У другому прикладі розмір масивів вже дорівнює . Отже, x = 14 і y = 42.