#366easyHeap

Kth Largest in Price Stream

Part of:Algorithms & Data Structures → Heaps & Priority Queues

Problem

A stream of stock prices arrives one at a time. After each new price, report the k-th largest price seen so far. If fewer than k prices have arrived, output -1.

Input Format

First line: integers n and k.
Second line: n space-separated prices.

Output Format

n space-separated integers — the k-th largest after each arrival.

Examples

Example 1

Input(First line: integers n and k.)

7 3
4 5 8 2 3 1 9

Output

4 4 4 4 4 3 5

After [4,5,8]: 3rd largest = 4. After adding 2: still 4. After adding 9: top 3 are [9,8,5], 3rd = 5.

Constraints

•1 ≤ n ≤ 10^5
•1 ≤ k ≤ n

Execution limits: 2s · 256MB

Loading interactive editor…