Алиса и Боб играют в игру. У Алисы есть массив a из n целых чисел, у Боба есть массив b из n целых чисел. За каждый ход игрок удаляет один элемент своего массива. Игроки ходят по очереди. Алиса ходит первой.
Игра заканчивается, когда оба массива содержат ровно один элемент. Пусть x будет последним элементом массива Алисы, а y — последним элементом массива Боба. Алиса хочет максимизировать абсолютную разницу между x и y, а Боб хочет минимизировать это значение. Оба игрока играют оптимально.
Найдите, какой будет окончательная стоимость игры.
Первая строка содержит целое число n (1 ≤ n ≤ 1000) - количество значений в каждом массиве.
Вторая строка содержит n целых чисел a[1]
, a[2]
, ..., a[n]
(1 ≤ a[i]
≤ 10^9
) - числа в массиве Алисы.
Третья строка содержит n целых чисел b[1]
, b[2]
, ..., b[n]
(1 ≤ b[i]
≤ 10^9
) - числа в массиве Боба.
Выведите абсолютную разницу между x и y, если оба игрока играют оптимально.
В первом примере x = 14 и y = 10. Таким образом, разница между этими двумя значениями составляет 4.
Во втором примере размер массивов уже равен 1. Следовательно, x = 14 и y = 42.