Use bucket-sort to order the keys, then use a union-find partition data structure to determine the answers to all the removeMin operations (but not necessarily in the order they appear in
S
).