Let \(c\) be the number of indices \(i\) such that \(A_{i+1} < A_i\). Then, \(\sum_{i=1}^{N-1} ((A_{i+1} - A_i) \bmod K) = A_N - A_1 + cK\). Now, let \(c'\) be the maximum value of \(c\). It can be seen that cases where \(c \le c'-2\) never yield an optimal solution, given that \(0 \le A_1,A_N < K\).

We determine \(c'\). As a trivial upper bound, when the same value appears \(d\) times in \(A\), we have \(c' \le N - d\). In other words, for the most frequent value in \(A\) that appears \(d'\) times, \(c' \le N - d'\). Moreover, this upper bound is achievable.

Thus, we have determined \(c'\). What remains is to maximize \(A_N - A_1\) for the cases where \(c=c'\) and \(c=c'-1\).

• For the case \(c=c'\)

In the proof above, let us maximize \(\min(B_{d'}) - \max(B_1)\). Here, the set of the most frequent values in \(A\), \(M_1,M_2,\dots,M_m(M_1 < M_2 < \dots < M_m)\), must be included in all \(B_i\). Hence, \(\min(B_{d'}) - \max(B_1) \le M_1 - M_m \). This upper bound is also achievable. (It can be shown that the values other than the most frequent ones can be added without influencing at least one of \(\min(B_{d'})\) and \(\max(B_1)\).)

• For the case \(c=c'-1\)

In the proof above, let us divide \(A\) into \(B_1,B_2,\dots,B_{d'+1}\). We maximize \(A_N - A_1 = \min(B_{d'+1}) - \max(B_1)\). The values in \(A\) other than the most frequent ones are placed into \(B_2,B_3,\dots,B_{d'}\). The most frequent values in \(A\) are placed into \(B_2,B_3,\dots,B_{d'}\), and then into either \(B_1\) or \(B_{d'+1}\). The optimal solution is such that for some integer \(x\), if \(M_i \le x\), it goes into \(B_1\), otherwise into \(B_{d'+1}\). Therefore, the maximum value of \(\min(B_{d'+1}) - \max(B_1)\) will be the maximum value of \(M_{i+1} - M_i\).

Therefore, calculating the above patterns solves the problem in \(\mathrm{O}(N\log N)\) time.