\(dist(l,r,x)\) は，\(dist(l,r,x)=\max(0,l-x,x-r)\) と書き直すことができます．

よって，最小化すべき関数は，\(\max(0,L_1-x,x-R_1,L_2-x,x-R_2,\cdots,L_k-x,x-R_k)\) となります． ここで，\(A_k=\max(L_1,L_2,\cdots,L_k)\)，\(B_k=\min(R_1,R_2,\cdots,R_k)\) とおくと，目的関数は \(\max(0,A_k-x,x-B_k)\) と書き直すことができます．

\(A_k \leq B_k\) のときは，\(x=A_k\) とすることで答えを \(0\) にすることができます． \(B_k < A_k\) のときは，\(x=\mathrm{floor}((A_k+B_k)/2)\) とするのが最適で，最小値 \(\mathrm{ceil}((A_k-B_k)/2)\) を達成できます．

結局，\(A_k,B_k\) をすべての \(k\) について順にもとめればよく，これは全体で \(O(N)\) 時間でできます．