最終的な数列の第 \(1\) 項目から決めていくことにします．第 \(1\) 項目の候補となりうるのは \(A_1,A_{K+1},A_{2K+1},\ldots\) のいずれかです．このうち最大値を \(m\) とするとき， 第 \(1\) 項目に割り当てるべきなのは \(A_{i}=m\) となる \(i\ (i \equiv 1 \pmod K)\) のうち最小のものとしてよいです．

証明： \(A_{i}=A_{j}=m (i<j, i\equiv j\equiv 1\mod K)\) となる \(i,j\) が存在するとする．最初の \(j-1\) 項を削除して得られる数列は，最初の \(i-1\) 項及び，第 \(i+1\) 項から第 \(j\) 項までを削除することによって得ることができる（ \(j-i\) は \(K\) の倍数であるため）．

第 \(2\) 項以降も同様の方針で決めていって良いです．各 \(i\) に対して， \(A_{i},A_{i+K},A_{i+2K},\ldots\) の累積 \(\max\) および最大値を与える最小の index を事前に計算することで \(O(N)\) で解けます．

実装例(Python)

n, k = map(int, input().split())
a = list(map(int, input().split()))
mx = [(0, 0)] * (n + k)
for i in range(n - 1, -1, -1):
    mx[i] = max((a[i], -i), mx[i + k])
ans = []
now = 0
while now < n:
    res, nxt = mx[now]
    ans.append(res)
    now = -nxt + 1
print(*ans)