#include <bits/stdc++.h>

#define rep(i, x, y) for (int i = (x), _ = (y); i <= _; ++i)
#define down(i, x, y) for (int i = (x), _ = (y); i >= _; --i)
#define x first
#define y second
#define mp make_pair
#define pb push_back
//#define LX_JUDGE

using namespace std;
typedef long long LL;

template<typename T> inline void upmax(T & x, T y) { x < y ? x = y : 0; }
template<typename T> inline void upmin(T & x, T y) { x > y ? x = y : 0; }

template<typename T>
inline void read(T & x) {
	char c;
	while ((c = getchar()) < '0' || c > '9');
	for (x = c - '0'; (c = getchar()) >= '0' && c <= '9'; x = x * 10 + c - '0');
}

const int inf = 0x3f3f3f3f;
const int N = 8 * 21005;

#define nt(x) ((x)<<1|1)
#define pt(x) ((x)<<1)

class TwoSat {
private :
	vector<int> adj[N];
	int dfn[N], low[N], tim;
	int sta[N], top;
	int col[N], scc, n, tot;

	void tarjan(int x) {
		dfn[x] = low[x] = ++tim;
		sta[++top] = x;
		for (int to : adj[x]) {
			if (dfn[to]) {
				if (!col[to]) {
					upmin(low[x], dfn[to]);
				}
			} else {
				tarjan(to);
				upmin(low[x], low[to]);
			}
		}
		if (dfn[x] == low[x]) {
			++scc;
			do {
				col[sta[top]] = scc;
			} while (sta[top--] != x);
		}
	}
public :
	void init(int n, int tot) {
		memset(col, 0, sizeof(int) * (tot));
		memset(dfn, 0, sizeof(int) * (tot));
		rep (i, 0, tot - 1) adj[i].clear();
		this->n = n;
		this->tot = tot;
	}
	inline void addEdge(int x, int y) {
		adj[x].pb(y ^ 1);
		adj[y].pb(x ^ 1);
	}
	inline void tadd(int x, int y) {
		adj[x].pb(y);
	}
	bool check() {
		top = tim = scc = 0;
		rep (i, 0, tot - 1) {
			if (!col[i]) {
				tarjan(i);
			}
		}
		rep (i, 0, n - 1) {
			if (col[pt(i)] == col[nt(i)]) {
				return 0;
			}
		}
		return 1;
	}
} my;

int A[N], poi[N];

inline bool cmp(int x, int y) {
	return A[x] < A[y];
}

class SegmentTree {
#define ls (o << 1)
#define rs (o << 1 | 1)
private :
	int id[N];
	int n, tot;

	inline void build(int o, int l, int r) {
		if (l == r) {
			id[o] = nt(poi[l]);
			return ;
		}
		id[o] = tot++;
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		my.tadd(id[o], id[ls]);
		build(rs, mid + 1, r);
		my.tadd(id[o], id[rs]);
	}

	int L, R, from;
	inline void addEdge(int o, int l, int r) {
		if (L <= l && r <= R) {
			my.tadd(from, id[o]);
			return ;
		}
		int mid = (l + r) >> 1;
		if (mid >= L)  addEdge(ls, l, mid);
		if (mid < R)  addEdge(rs, mid + 1, r);
	}
public :
	inline void build(int n) {
		this->n = n;
		tot = n * 4;
		build(1, 0, n * 2 - 1);
	}
	inline void add(int fr, int l, int r) {
		from = fr, L = l, R = r;
		addEdge(1, 0, n * 2 - 1);
	}
#undef ls
#undef rs
} T;

int n;

bool check(int v) {
	my.init(n * 2, n * 6);
	T.build(n);
	rep (i, 0, n - 1) {
		my.addEdge(nt(i), nt(i + n));
	}
	rep (i, 0, n * 2 - 1) {
		A[poi[i]] -= v;
		int l = lower_bound(poi, poi + i, poi[i], cmp) - poi;
		A[poi[i]] += v;
		A[poi[i]] += v;
		int r = upper_bound(poi + i + 1, poi + n * 2, poi[i], cmp) - poi;
		A[poi[i]] -= v;
		if (l < i) {
			T.add(pt(poi[i]), l, i - 1);
		}
		if (i < r - 1) {
			T.add(pt(poi[i]), i + 1, r - 1);
		}
	}
	return my.check();
}

#undef pt
#undef nt

int main() {
#ifdef LX_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	read(n);
	rep (i, 0, n - 1) {
		read(A[i]), read(A[i + n]);
	}
	rep (i, 0, n * 2 - 1) {
		poi[i] = i;
	}
	sort(poi, poi + n * 2, cmp);
	int l = 0, r = inf;
	while (l <= r) {
		int mid = (l + r) / 2;
		check(mid) ? l = mid + 1 : r = mid - 1;
	}
	cout << l << endl;
    return 0;
}


Measured memory_bytes: 14976