Challenge: Live Leaderboard

Lab Java Intermediate 20 points

Scores arrive one at a time. After each score, print the current k-th highest score so far, or - if fewer than k scores have arrived. Keep a min-heap of size k.

Input

Line 1: n k. Line 2: n scores in arrival order.

Output

n answers separated by spaces.

Example

Input

6 3
50 20 80 70 10 90

Output

- - 20 50 50 70

Sample input available Sample output available

Editor

Java

Hints

Min-heap of at most k scores: offer, and poll if the size goes over k.

Once it holds k scores, peek() is exactly the k-th highest.

Solution explanation

Each score is O(log k), so the whole stream is O(n log k) – and it never stores more than k scores.

Show solution

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        PriorityQueue<Integer> top = new PriorityQueue<Integer>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            top.offer(sc.nextInt());
            if (top.size() > k) top.poll();
            if (i > 0) sb.append(' ');
            sb.append(top.size() < k ? "-" : String.valueOf(top.peek()));
        }
        System.out.println(sb);
    }
}

Output

Answer