#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
#define INF 10000000000ll
#define N 200020
#define M N<<5
template<typename TP> inline void read(TP &ret)
{
    TP x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    ret=(TP)x*f;
}
int n;
struct apple
{
    int to,next;
}indexx[M];
int head[N+(N<<2)],cnt;
void init(int x,int y)
{
    indexx[++cnt].to=y;
    indexx[cnt].next=head[x];
    head[x]=cnt;
}
struct lemon
{
    lint v;
    int id;
    lemon(){}
    lemon(lint v,int id):v(v),id(id){};
    bool operator<(const lemon &other)const
    {
        return v<other.v;
    }
}point[N<<2];
int point_id;
lint maxn,minn;
int pos[N];
int tot;
struct segment_tree
{
    int l,r,lson,rson;
}tree[N+(N<<2)];
void push_up(int now)
{
    init(now,tree[now].lson);
    init(now,tree[now].rson);
}
void build(int &now,int l,int r)
{
    now=++tot;
    tree[now].l=l,tree[now].r=r;
    if(l==r)
    {
        init(now,point[l].id<=n?point[l].id+n:point[l].id-n);
        return;
    }
    int mid=(l+r)>>1;
    build(tree[now].lson,l,mid);
    build(tree[now].rson,mid+1,r);
    push_up(now);
    return;
}
void add(int now,int l,int r,int p)
{
    if(l<=tree[now].l&&r>=tree[now].r)
    {
        init(p,now);
        return;
    }
    int mid=(tree[now].l+tree[now].r)>>1;
    if(l<=mid) add(tree[now].lson,l,r,p);
    if(r>mid) add(tree[now].rson,l,r,p);
}
int dfn[N+(N<<2)],low[N+(N<<2)],dfn_id,st[N+(N<<2)],top,circs,belong[N+(N<<2)];
bool used[N+(N<<2)];
void tarjan(int u)
{
    dfn[u]=low[u]=++dfn_id;
    st[++top]=u;
    used[u]=1;
    for(int i=head[u];i;i=indexx[i].next)
    {
        int v=indexx[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(used[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        int v=-1;
        circs++;
        while(v!=u)
        {
            v=st[top--];
            used[v]=0;
            belong[v]=circs;
        }
    }
}
bool SAT()
{
    for(int i=1;i<=point_id;i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(belong[i]==belong[i+n]) return 0;
    }
    return 1;
}
bool check(lint mid)
{
    cnt=0;
    tot=point_id;
    memset(head,0,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(used,0,sizeof(used));
    top=0;
    circs=0;
    int root;
    build(root,1,point_id);
    int head,tail;
    head=tail=1;
    for(int i=1;i<=point_id;i++)
    {
        int op,p=point[i].id;
        if(p<=n) op=pos[p+n];
        else op=pos[p-n];
        while(tail<=i&&point[tail].v+mid<point[i].v) tail++;
        if(tail<i&&tail>=1&&point[tail].v+mid>point[i].v)
        {
            if(tail<=op&&op<i)
            {
                if(op<i-1) add(root,op+1,i-1,p);
                if(tail<op) add(root,tail,op-1,p);
            }
            else
            {
                add(root,tail,i-1,p);
            }
        }
        while(head<=point_id&&point[head].v-mid<point[i].v) head++;
        head--;
        if(head>i&&head<=point_id&&point[head].v-mid<point[i].v)
        {
            if(head>=op&&op>i)
            {
                if(op>i+1) add(root,i+1,op-1,p);
                if(head>op) add(root,op+1,head,p);
            }
            else
            {
                add(root,i+1,head,p);
            }
        }
    }
    return SAT();
}
int main()
{
    read(n);
    maxn=-INF,minn=INF;
    for(int i=1;i<=n;i++)
    {
        lint x,y;
        read(x),read(y);
        point[++point_id]=lemon(x,i);
        point[++point_id]=lemon(y,n+i);
        maxn=max(maxn,max(x,y));
        minn=min(minn,min(x,y));
    }
    sort(point+1,point+point_id+1);
    for(int i=1;i<=point_id;i++)
    {
        pos[point[i].id]=i;
    }
    lint l=0,r=maxn,mid,ans;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid))
        {
            l=mid+1;
            ans=mid;
        }
        else
        {
            r=mid;
        }
    }
    printf("%lld\n",ans);
}

Measured memory_bytes: 34944