K-th greatest value in every growing prefix

You are given arr, a permutation of the integers 1 to n (each value appears exactly once), and an integer k with 1 <= k <= n.

Read arr from left to right. After reading each prefix of length i, for every i from k to n, report the k-th greatest value in that prefix. Return the n - k + 1 answers in order.

def kth_greatest_in_prefixes(arr: list[int], k: int) -> list[int]: ...

Constraints

• 1 <= n <= 10^5
• arr is a permutation of 1..n
• 1 <= k <= n

Example 1

arr = [3, 1, 4, 2, 5], k = 2
output: [1, 3, 3, 4]

Prefix [3, 1]: the 2nd greatest value is 1. Add 4 to get [3, 1, 4]: the answer is 3. Add 2: still 3. Add 5: the top two are 5 and 4, so the answer is 4.

Example 2

arr = [4, 3, 2, 1], k = 1
output: [4, 4, 4, 4]

With k = 1 the answer is the running maximum.

Aim for better than sorting every prefix. Then say whether the fact that arr is a permutation lets you do better still.

Reconstructed from the reported question; details may differ from what interviewers ask.