\(N=1\) の場合は簡単に解けます.
\(2 \leq N\) の場合は、高々\(N-1\) 回の操作で \(A\) の長さが \(N-1\) の場合に帰着でき、操作回数は高々 \( \sum_{i=1}^{N}(i-1) \) 回となり、これは \(5×10^5\) 以下となります .
具体的には \(x\) \(\in\) \( \underset{1 \leq i \leq N}{\operatorname{argmax}} \) \(A _ {i} +K(N-i)\) を満たす \(x\) を一つ取り、 \(i\) を \(x,x+1...N-1\) の順に選択して操作を行います.
実はこの後に \(A _ {N-1} \gt A _ {N}\) となってしまうようなことはありません.
これは \(N \leftarrow N-1\) 、 \(A \leftarrow A _ 1,A _ 2...A _ {x-1} ,A _ {x+1} ... A _ {N-1} ,A _{N} \) としたときに \(\max(A _ {i}+K(N-i))\) は非増加であることから簡単にわかります.

\(\min(A)\)を先頭に移動させる操作を繰り返す解法でもACできます.