#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

struct two_sat {
    int n = 0;
    vector<vector<int>> adj;
    vector<bool> assignment;

    int inv(int var) {
        return var ^ 1;
    }

    int new_var() {
        adj.emplace_back();
        adj.emplace_back();
        return 2 * n++;
    }

    void implies(int a, int b) {
        adj[a].push_back(b);
        adj[inv(b)].push_back(inv(a));
    }

    void either(int a, int b) {
        adj[inv(a)].push_back(b);
        adj[inv(b)].push_back(a);
    }

    void set_value(int a) {
        adj[inv(a)].push_back(a);
    }

    void equal(int a, int b) {
        implies(a, b);
        implies(inv(a), inv(b));
    }

    void unequal(int a, int b) {
        implies(a, inv(b));
        implies(inv(a), b);
    }

    // Warning: this only creates an implication in the negative direction. It is still possible for
    // a = b = true with and_var = false. In particular, it does not work to call set_value on inv(and_var).
    int create_and(int a, int b) {
        if (a < 0 || b < 0) return max(a, b);
        int result = new_var();
        implies(result, a);
        implies(result, b);
        return result;
    }

    // Warning: this only creates an implication in the positive direction. It is still possible for
    // a = b = false with or_var = true. In particular, it does not work to call set_value on or_var.
    int create_or(int a, int b) {
        if (a < 0 || b < 0) return max(a, b);
        int result = new_var();
        implies(a, result);
        implies(b, result);
        return result;
    }

    int create_at_most_one(int a, int b) {
        if (a < 0 || b < 0) return max(a, b);
        either(inv(a), inv(b));
        return create_or(a, b);
    }

    template<typename T_iterable>
    int create_at_most_one(const T_iterable &vars) {
        int aux = -1;

        for (int var : vars)
            aux = create_at_most_one(aux, var);

        return aux;
    }

    bool solve() {
        assignment.assign(2 * n, false);
        vector<bool> vis[2];
        vector<int> q[2];
        vis[0].assign(2 * n, false);
        vis[1].assign(2 * n, false);
        q[0].resize(2 * n);
        q[1].resize(2 * n);

        for (int i = 0; i < n; i++) {
            if (!assignment[2 * i] && !assignment[2 * i + 1]) {
                // we have to do the search
                bool bad[2] = {false, false};
                int qs[2] = {0, 0};
                int qi[2] = {0, 0};
                int qt[2] = {0, 0};

                for (int z = 0; z < 2; z++) {
                    vis[z][2 * i + z] = true;
                    q[z][qt[z]++] = 2 * i + z;
                }

                while (true) {
                    if (bad[0] && bad[1])
                        return false;

                    for (int z = 0; z < 2; z++) {
                        if (bad[z])
                            continue;

                        if (qs[z] >= qt[z]) {
                            // we're done, so we should finalize it
                            for (int ind = 0; ind < qt[z]; ind++)
                                assignment[q[z][ind]] = true;

                            bad[!z] = true;
                            goto done;
                        }

                        int v = q[z][qs[z]];

                        if (qi[z] == int(adj[v].size())) {
                            qs[z]++;
                            qi[z] = 0;
                            continue;
                        }

                        int u = adj[v][qi[z]];
                        assert(!assignment[inv(u)]);

                        if (vis[z][inv(u)]) {
                            bad[z] = true;
                        } else if (!assignment[u] && !vis[z][u]) {
                            vis[z][u] = true;
                            q[z][qt[z]++] = u;
                        }

                        qi[z]++;
                    }
                }

done:
                assert(bad[0] ^ bad[1]);

                // reset vis
                for (int z = 0; z < 2; z++)
                    for (int ind = 0; ind < qt[z]; ind++)
                        vis[z][q[z][ind]] = false;
            }

            assert(assignment[2 * i] ^ assignment[2 * i + 1]);
        }

        return true;
    }
};


const int INF = 1e9 + 5;

int N, T;
vector<pair<int, int>> sorted;
two_sat solver;
vector<int> tree;

void build_tree() {
    T = 2 * N;
    tree.assign(2 * T, -1);

    for (int t = 1; t < 2 * T; t++)
        tree[t] = solver.new_var();

    for (int t = 2; t < 2 * T; t++)
        solver.implies(tree[t / 2], tree[t]);

    for (int t = 0; t < T; t++)
        solver.implies(tree[T + t], solver.inv(sorted[t].second));
}

void add_range(int from, int start, int end) {
    for (start += T, end += T; start < end; start /= 2, end /= 2) {
        if (start & 1)
            solver.implies(from, tree[start++]);

        if (end & 1)
            solver.implies(from, tree[--end]);
    }
}

bool possible(int d) {
    solver = two_sat();

    for (int i = 0; i < N; i++)
        solver.new_var();

    build_tree();

    for (int i = 0; i < T; i++) {
        int start = lower_bound(sorted.begin(), sorted.end(), make_pair(sorted[i].first - d + 1, 0)) - sorted.begin();
        int end = lower_bound(sorted.begin(), sorted.end(), make_pair(sorted[i].first + d, 0)) - sorted.begin();
        add_range(sorted[i].second, start, i);
        add_range(sorted[i].second, i + 1, end);
    }

    return solver.solve();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        sorted.emplace_back(x, 2 * i);
        sorted.emplace_back(y, 2 * i + 1);
    }

    sort(sorted.begin(), sorted.end());
    int low = 0, high = INF;

    while (low < high) {
        int mid = (low + high + 1) / 2;

        if (possible(mid))
            low = mid;
        else
            high = mid - 1;
    }

    cout << low << '\n';
}


Measured memory_bytes: 13704