ダイヤルが \(9\) と \(0\) の間を行き来すると扱いづらいので、\(A_i\equiv B_i \pmod {10}\) なる \(B_i\) を適切に選んで考えます。 区間に \(1\) を足したり引いたりすることで、もとの数列を \(B_i\) に変更する最小回数を求めればよいです。

ここで、\(B_0=B_{N+1}=0, C_i = B_i - B_{i+1}(0\leq i\leq N)\) とします。 このとき、問題文中の操作は、\(0\leq i,j\leq N\) なる \(i,j\) を任意に選んで、\(C_i\) に \(1\) を足し、\(C_j\) から \(1\) を引くという操作に言い換えられます。\(B_0=B_{N+1}\) ですから、答えは \(\frac{\sum |C_i|}{2}\) となります。

\(\sum|C_i|\) を最小化する方法を考えましょう。これは、最初 \(B_i=A_i(1\leq i\leq N)\) とし、次のように \(C\) を操作することで達成できます。

• \(C\) の要素を正負で分けて絶対値の降順にソートし、絶対値の大きい順に二つの数を見る。このとき、負の側に \(10\) を足し、正の側から \(10\) を引いて絶対値の和が小さくなれば、そのように変更を加える。

ソートがボトルネックとなって、この問題を \(O(N\log N)\) で解けました。