Problem

You are given a permutation of integers from 1 to n stored in an array arr, and an integer k. The ith greatest element of an array is the ith element when sorted in decreasing order.

For each prefix of the array of length i (where i ranges from k to n), find the kth greatest element.

Hint: Try to think about min-heap

Input

• int arr[n] : a permutation of n integers
• int k : the rank of the element to find

Output

• int[n - k + 1] : answers for each ith prefix in the range [k, n].

Example

n = 4 k = 2 arr = [4, 2, 1, 3]

Find the 2nd greatest element for each prefix of size i ≥ k:

• i = 2, arr = [4, 2] → The 2nd greatest element is 2
• i = 3, arr = [4, 2, 1] → The 2nd greatest element is 2
• i = 4, arr = [4, 2, 1, 3] → The 2nd greatest element is 3

Return the array [2, 2, 3].