\(dist(l,r,x)\) can be rephrased into \(dist(l,r,x)=\max(0,l-x,x-r)\).

Thus, the function to minimize is \(\max(0,L_1-x,x-R_1,L_2-x,x-R_2,\cdots,L_k-x,x-R_k)\). Here, if we let \(A_k=\max(L_1,L_2,\cdots,L_k)\) and \(B_k=\min(R_1,R_2,\cdots,R_k)\), the objective function can be rephrased into \(\max(0,A_k-x,x-B_k)\).

If \(A_k \leq B_k\), we can let \(x=A_k\) to make the answer \(0\). If \(B_k < A_k\), the optimal choice is \(x=\mathrm{floor}((A_k+B_k)/2)\), which achieves the minimum value \(\mathrm{ceil}((A_k-B_k)/2)\).

In the end, we need to find \(A_k\) and \(B_k\) for every \(k\) in order, which can be done in \(O(N)\) time in total.