The Table That Doubles Before It Clogs

A linear-probing table starts with start slots, a power of two. Keys are inserted one at a time.

Probes. Inserting a key examines slots from key % m onwards until it reaches an empty one; every slot examined, including the one finally written, counts as one probe.

Growth. After an insertion, if the number of stored keys is more than half the slots, the table doubles and every stored key is reinserted into the new table in its original insertion order. Those reinsertions are counted as probes too.

Write resizing_table(keys, start) returning the tuple (final_m, total_probes).

Examples

Input:  keys = [1, 2, 3], start = 4
Output: (8, 6)
Explanation: three insertions find an empty slot at once (3 probes), the third pushes the load above a half, and rehashing the three keys into 8 slots costs 3 more.

Input:  keys = [0, 1], start = 2
Output: (4, 4)

Constraints

• 1 <= len(keys) <= 20000, keys are distinct, 0 <= key <= 10**9
• start is a power of two, 1 <= start <= 1024

Goals

• Count the probes an open-addressed table really performs
• Grow the table when the load factor passes a half and rehash everything
• See that the rehashing cost, spread over the insertions, stays constant per key