All problems

Ski Lift Waits

Medium · heap

The operator of a ski lift writes down how long each skier waited, in minutes, as the skiers board. waits[i] is the wait of the i-th skier to board.

After each skier boards, the operator wants the fast-third mark. Take every wait written down so far, say there are c of them, and sort them from smallest to largest. The quickest third is the first ceil(c / 3) waits in that order, and the mark is the largest wait inside it, which is the last of those waits.

Return a list with the mark after each skier boards, in boarding order.

Examples

Example 1

Input: waits = [9, 9, 4, 7, 6, 8, 1]

Output: [9, 9, 4, 7, 6, 6, 6]

After three skiers the sorted waits are 4, 9, 9 and the quickest third is just 4. After the fourth they are 4, 7, 9, 9 and the quickest third is the first two, so the mark is 7.

Example 2

Input: waits = [5, 2, 8, 1, 9, 3]

Output: [5, 2, 2, 2, 2, 2]

Example 3

Input: waits = [3]

Output: [3]

Constraints