Rebuild the Photo Line

Before a team photo, the players stood in a single-file line. Each player noted two numbers: their height, and how many players in front of them were at least as tall as they are. Then the notes were shuffled.

people is a list of (height, ahead) tuples, one per player, in no particular order. Write rebuild_line(people) that returns the line from front to back as a list of the same (height, ahead) tuples. The notes always come from a real line, and exactly one line fits them.

Examples

rebuild_line([(175, 2), (160, 5), (182, 0), (165, 2), (182, 1), (170, 0)])
# returns [(170, 0), (182, 0), (165, 2), (182, 1), (175, 2), (160, 5)]

rebuild_line([(150, 1), (160, 0)])
# returns [(160, 0), (150, 1)]

rebuild_line([(155, 2), (155, 0), (155, 1)])
# returns [(155, 0), (155, 1), (155, 2)]

In the first example the player of height 165 has two players at least as tall in front: 170 and 182. The second player of height 182 counts the first one, because equal heights count as at least as tall.

Constraints

• 0 <= len(people) <= 20,000
• 1 <= height <= 10^6
• 0 <= ahead < len(people)