절댓값 게임

Alice와 Bob이 게임을 한다. Alice는 정수 n개로 이루어진 배열 a를, Bob은 정수 n개로 이루어진 배열 b를 가지고 있다. 각 턴에서 플레이어는 자신의 배열에서 원소 하나를 제거한다. 두 플레이어는 번갈아 가며 턴을 진행하고, Alice가 먼저 시작한다.

두 배열에 원소가 각각 하나씩만 남으면 게임이 끝난다. Alice의 배열에 마지막으로 남은 원소를 x, Bob의 배열에 마지막으로 남은 원소를 y라고 하자. Alice는 x와 y의 절댓값 차이를 최대화하려 하고, Bob은 이 값을 최소화하려 한다. 두 플레이어 모두 최적으로 플레이한다.

게임의 최종 값을 구하시오.

첫째 줄에 정수 n (1 ≤ n ≤ 1 000)이 주어진다. 이는 각 배열에 들어 있는 값의 개수이다.

둘째 줄에 n개의 정수 a1, a2, . . . , an (1 ≤ ai ≤ 109)이 공백으로 구분되어 주어진다. 이는 Alice의 배열에 들어 있는 수이다.

셋째 줄에 n개의 정수 b1, b2, . . . , bn (1 ≤ bi ≤ 109)이 공백으로 구분되어 주어진다. 이는 Bob의 배열에 들어 있는 수이다.

두 플레이어가 최적으로 플레이할 때 x와 y의 절댓값 차이를 출력한다.

첫 번째 예시에서 x = 14, y = 10이다. 따라서 두 값의 차이는 4이다.

두 번째 예시에서는 배열의 크기가 이미 1이다. 따라서 x = 14, y = 42이다.