G - Absolute Game

G - Absolute Game

Alice and Bob are playing a game. Alice has an array aa of nn integers, Bob has an array bb of nn 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.

Input

The first line contains a single integer n (1≤n≤1000) — the number of values in each array.

The second line contains nn space-separated integers a1,a2,…,an (1≤ai≤109) — the numbers in Alice's array.

The third line contains nn space-separated integers b1,b2,…,bn (1≤bi≤109) — the numbers in Bob's array.

Output

Print the absolute difference between xx and yy if both players are playing optimally.

Examples

Input

4
2 14 7 14
5 10 9 22

Output

4

Input

1
14
42

Output

28

Note

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

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

题目链接：https://vjudge.net/contest/345791#problem/G

试题解析 

我们先对a,b两个数组求最小差值数组c，即ci=min(abs(ai-bj))。

我们知道存在bi使得ai与bi的差值最小，所以每当Alice去掉一个ai时，Bob就去掉与之对应的bi，为什么去掉bi？

当a数组与b数组取最小值是一一对应时，我们知道bi是使ai为最小的所以去掉ai后，bi不会使得a数组中其他数的最小值变得更小，所以Bob此时去掉相应的bi。Alice丢弃一个数时一定是将使得ci值最小的数去掉，到最后我们就会发现我们得到的值就是ci数组的中的最大值。

当a数组与b数组取最小值不是一一对应时，Alice还是会去掉使得ci值最小的那一个ai，当存在aj==ai时就说明会有一个b不会使得任何一个a最小，此时Bob就会去掉这个数b，到最后得到的值还是ci数组中的最大值。

所以我们只需要将ci数组求出来再找到最小值就好了。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int mx=2e5+10;
int s1[mx],s2[mx];
int n;

int main()
{
	int ans=-1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&s1[i]);
	for(int i=1;i<=n;i++)
	scanf("%d",&s2[i]);
	for(int i=1;i<=n;i++)
	{
		int m=inf;
		for(int j=1;j<=n;j++)
		{
			m=min(m,abs(s1[i]-s2[j]));
		}
		ans=max(ans,m);
	}
	printf("%d\n",ans);
	return 0;
}