For simplicity, we assume that \(A_i\) are distinct. Once we solve it for distinct \(A_i\), so do we for the original one by an appropriate tie-breaking by, say, the pairs \((A_i, i)\).

We cannot actually sort \(A_i, \dots, A_{i+M-1}\) for each \(i\) within the execution time limit. Here, notice that incrementing \(i\) does not really changes the first \(K\) terms of \(A_i, \dots, A_{i+M-1}\) sorted in ascending order.
Let \(L\) be the set of the \(K\) smallest values among \(A_i, \dots, A_{i+M-1}\), and \(R\) be the set of the others. The answer is the sum of values belonging to \(L\), so it is sufficient to update \(L\) and \(R\) fast enough every time \(i\) increases.

The definition of \(L\) and \(R\) is equivalent to the following conditions:

• \(|L| = K\)
• \(L \cup R = \{A_i, \dots, A_{i+M-1}\}\)
• \(\max L \lt \min R\)

The third condition is due to the assumption that \(A_i\) are distinct. Every time \(i\) is incremented, \(A_i\) is removed and \(A_{i+M}\) is inserted. Let us temporarily forget the condition \(|L| = K\) and only try to preserve the other two; then we come up with the following steps:

• Determine whether \(A_i\) belongs to \(L\) or \(R\). Remove \(A_i\) from the set.
• If \(A_{i+M} \lt \max L\), insert \(A_{i+M}\) to \(L\); otherwise, insert it to \(R\).

After this process, \(|L| = K\) is not guaranteed, but \(K - 1 \leq |L| \leq K+1\) still holds, so we can move at most one element from \(L\) to \(R\) or vice versa to satisfy \(|L| = K\) again.

Each operation so far can be achieved in an \(O(\log N)\) time with a data structure that stores an ordered set. After finding \(L\) and \(R\) for \(i = 1\), we can scan \(i\) one by one, so that the original problem is solved in a total of \(O(N \log N)\) time.