\(i\) 番目の人の時点での最小の労力を \(S(i)\) とすると,

\[S(i) = \min_{1 \leq j \leq i} \{ S(j-1) + \vert a_i-x_j \vert + y_j \}\]

となる. ここで \(a_i \geq x_j\) となる \(j\) の最大値を \(j_1\), \(a_i \lt x_j\) となる \(j\) の最小値を \(j_2\) とすると,

\[S(i) = \min\left( \min_{1 \leq j \leq j_1} \{ S(j-1)+y_j-x_j \} + a_i, \min_{j_2 \leq j \leq i} \{ S(j-1)+y_j+x_j \} - a_i \right)\]

となる. \(j_1, j_2\) は二分探索で探し, \(S(j-1)+y_j \pm x_j\) はそれぞれ最小値を計算するセグメントツリーで管理すればいい.