Flags

#include <bits/stdc++.h>

#define X first
#define Y second

using namespace std;

typedef pair<int, int> pii;

const int OFFSET = 1 << 15, INF = 1e9 + 5;

int n, helper[OFFSET], opposite[OFFSET];
vector<pii> pos;
vector<int> adj[2 * OFFSET], adjrev[2 * OFFSET];

pii nodeval[2 * OFFSET];
void build(int node = 1){
    if(node >= OFFSET){
        int ind = node - OFFSET;
        if(ind < pos.size()) nodeval[node] = {pos[ind].X, pos[ind].X};
        return;
    }

    adj[node].push_back(2 * node);
    adj[node].push_back(2 * node + 1);

    adjrev[2 * node].push_back(node);
    adjrev[2 * node + 1].push_back(node);

    build(2 * node);
    build(2 * node + 1);

    nodeval[node] = {
        min(nodeval[2 * node].X, nodeval[2 * node + 1].X),
        max(nodeval[2 * node].Y, nodeval[2 * node + 1].Y) };
}

void connect(int thing, int lo, int hi, int node = 1, int l = 0, int r = OFFSET){
    if(l >= 2 * n) return;
    if(nodeval[node].X >= lo && nodeval[node].Y <= hi && (opposite[thing - OFFSET] < l || opposite[thing - OFFSET] >= r)){
        adj[thing].push_back(node);
        adjrev[node].push_back(thing);
        return;
    }
    if(nodeval[node].X > hi || nodeval[node].Y < lo) return;
    if(r - l == 1) return;

    int m = (l + r) / 2;
    connect(thing, lo, hi, 2 * node, l, m);
    connect(thing, lo, hi, 2 * node + 1, m, r);
}

vector<int> scc_stack;
bool bio[2 * OFFSET];
void scc_dfs1(int node){
    if(bio[node]) return;
    bio[node] = true;

    for(auto nxt : adj[node]) scc_dfs1(nxt);

    scc_stack.push_back(node);
}

int scc[2 * OFFSET];
void scc_dfs2(int node, int comp){
    if(scc[node]) return;
    scc[node] = comp;

    for(auto nxt : adjrev[node]) scc_dfs2(nxt, comp);
}

void cleanup(){
    for(int i = 0; i < 2 * n; i++){
        adj[OFFSET + i].clear();
    }

    for(int i = 1; i < 2 * OFFSET; i++){
        adjrev[i].clear();
        if(i > 1) adjrev[i].push_back(i / 2);
    }

    memset(bio, 0, sizeof bio);
    memset(scc, 0, sizeof scc);
    scc_stack.clear();
}

bool evaluate(int dist){
    cleanup();

    for(int i = 0; i < 2 * n; i++) connect(OFFSET + opposite[i], pos[i].X - dist + 1, pos[i].X + dist - 1);

    scc_dfs1(1);
    reverse(scc_stack.begin(), scc_stack.end());

    int comp = 0;
    for(auto node : scc_stack){
        if(scc[node] == 0) scc_dfs2(node, ++comp);
    }

    for(int i = 0; i < 2 * n; i++){
        if(scc[OFFSET + i] == scc[OFFSET + opposite[i]]) return false;
    }

    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;

        pos.push_back({a, i});
        pos.push_back({b, i});
    }

    sort(pos.begin(), pos.end());
    memset(helper, -1, sizeof helper);
    for(int i = 0; i < pos.size(); i++){
        if(helper[pos[i].Y] == -1) helper[pos[i].Y] = i;
        else{
            opposite[i] = helper[pos[i].Y];
            opposite[helper[pos[i].Y]] = i;
        }
    }

    build();

    int l = 0, r = INF;
    while(r > l){
        int m = (l + r + 1) / 2;

        if(evaluate(m)) l = m;
        else r = m - 1;
    }

    cout << l << '\n';

    return 0;
}