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).