Kth Greatest in Expanding Prefix

Question

You are given arr, a permutation of the integers 1 through n in which every integer occurs once, along with an integer k. Consider each prefix length i from k up to n, both included. For each one, find the k-th greatest value among the first i elements of arr. ...