\(A_{i+1} < A_i\) を満たす \(i\) の個数を \(c\) とします。すると、\(\sum_{i=1}^{N-1} ((A_{i+1} - A_i) \bmod K) = A_N - A_1 + cK\) が成り立ちます。さて、\(c\) の最大値を \(c'\) とします。すると、\(0 \le A_1,A_N < K\) より \(c \le c'-2\) のケースは必ず最適解にならないことが分かります。

\(c'\) を求めます。自明な上界として、\(A\) に同じ値が \(d\) 個現れるとき、\(c' \le N - d\) です。つまり、\(A\) の最頻値の現れる回数 \(d'\) に対して \(c' \le N - d'\) となります。そして、この上界は実際に達成可能です。

よって、\(c'\) が求まりました。あとは、\(c=c',c'-1\) の場合でそれぞれ \(A_N - A_1\) を最大化すればよいです。

・\(c=c'\) の場合

上記の証明において、\(A_N - A_1 = \min(B_{d'}) - \max(B_1)\) を最大化します。 ここで、\(A\) での最頻値の集合 \(M_1,M_2,\dots,M_m(M_1 < M_2 < \dots < M_m)\) は必ず全ての \(B_i\) に含まれています。つまり、\(\min(B_{d'}) - \max(B_1) \le M_1 - M_m \) が成り立ちます。 そして、この上界も達成可能です。(最頻値以外は \(\min(B_{d'}),\max(B_1)\) の少なくともどちらかの影響がないように加えることが示せます。)

・\(c=c'-1\) の場合

上記の証明において、\(A\) を \(B_1,B_2,\dots,B_{d'+1}\) に分割すればよいです。\(A_N - A_1 = \min(B_{d'+1}) - \max(B_1)\) を最大化します。\(A\) の最頻値以外は \(B_2,B_3,\dots,B_{d'}\) に入れます。\(A\) の最頻値を \(B_2,B_3,\dots,B_{d'}\) に入れたうえで \(B_1,B_{d'+1}\) のどちらかに入れます。最適解はある整数 \(x\) に対して \(M_i \le x\) なら \(B_1\) に、そうでないなら \(B_{d'+1}\) に入れる形になります。つまり、\(\min(B_{d'+1}) - \max(B_1)\) の最大値は \(M_{i+1} - M_i\) の最大値となります。

よって、上記の \(2\) パターンを両方求めることで \(\mathrm{O}(N\log N)\) でこの問題を解くことが出来ます。