{"problem":{"name":"Range Point Distance","description":{"content":"For integers $l$, $r$, and $x$ ($l \\leq r$), let us define $dist(l,r,x)$ as follows. *   If $x<l$: $dist(l,r,x)=l-x$ *   If $l \\leq x \\leq r$: $dist(l,r,x)=0$ *   If $r<x$: $dist(l,r,x)=x-r$ You are","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc129_b"},"statements":[{"statement_type":"Markdown","content":"For integers $l$, $r$, and $x$ ($l \\leq r$), let us define $dist(l,r,x)$ as follows.\n\n*   If $x<l$: $dist(l,r,x)=l-x$\n*   If $l \\leq x \\leq r$: $dist(l,r,x)=0$\n*   If $r<x$: $dist(l,r,x)=x-r$\n\nYou are given $N$ pairs of integers, the $i$\\-th of which is $(L_i,R_i)$. For each $k=1,2,\\cdots,N$, solve the following problem.\n\n*   Let us choose an integer $x$ freely and compute $\\max(dist(L_1,R_1,x),dist(L_2,R_2,x),\\cdots,dist(L_k,R_k,x))$. Find the minimum possible value of this.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq L_i \\leq R_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_N$ $R_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc129_b","tags":[],"sample_group":[["3\n1 3\n2 4\n5 6","0\n0\n1\n\n*   For $k=1$, an optimal choice is $x=1$.\n*   For $k=2$, an optimal choice is $x=3$.\n*   For $k=3$, an optimal choice is $x=4$."],["10\n64 96\n30 78\n52 61\n18 28\n9 34\n42 86\n11 49\n1 79\n13 59\n70 95","0\n0\n2\n18\n18\n18\n18\n18\n18\n21"]],"created_at":"2026-03-03 11:01:14"}}