\(a_i, a_j\) の順にジャンプすることを考えます。すると、場所は \(2a_j - (2a_i - x) = x + 2 (a_j - a_i)\) です。

もう一回 \(a_k\) でジャンプすると、場所は \(-x + 2 (a_k -a_j +a_i)\) です。これを見ると、 \(x\) の係数は偶奇によって \(-1, 1\) に変わるだけに気付きます。

一般に、 \(b_1, b_2, \cdots, b_{2k+1}\) についてジャンプすると

\[-x + 2(b_1 - b_2 + b_3 - \cdots + b_{2k+1})\]

\(b_1, b_2, \cdots, b_{2k}\) についてジャンプすると

\[x + 2(- b_1 + b_2 - b_3 + \cdots + b_{2k})\]

に移動します。 \(s\) から \(t\) にいくために、たとえば奇数回ジャンプするときは

\[b_1 - b_2 + b_3 - \cdots + b_{2k+1} = \frac{s+t}{2}\]

偶数回ジャンプするときは

\[- b_1 + b_2 - b_3 + \cdots + b_{2k+1} = \frac{-s+t}{2}\]

となります。これはほとんど部分和問題です。

\(dp[x][m]\) を、mod 2 で \(m\) 回使って合計が \(x\) であるとき、使用回数の最小とします。初期値は \(dp[0][0] = 0\) として、BFS を行えばよいです。遷移1回ごとに計算量 \(O(N)\) がかかります。

ここで、\(M=|\max a|\) として \(|x| \le M + \max(|\frac{s_i-t_i}{2}|, |\frac{s_i+t_i}{2}|)\) に限定してもよいです。なぜなら、 \(b_{2i} - b_{2i+1}\) を 1 ブロックにすると、値の範囲は \([-M , +M]\) で、最終的に部分和が \(v\) になるとき、任意に \(b_{2i} - b_{2i+1}\) を並び替えると（具体的に、現在総和が負なら正の要素を出来るだけ使い、現在総和が正なら負の要素を出来るだけ使うことで）常に \([-v, +v]\) に収まるからです。