Summarising a Billion Dice

A games company logged how often each result came up in an enormous number of rolls of its special dice. The log is a tally: a dictionary from a result (a whole number, possibly negative) to how many times it occurred. The counts are far too large to write the rolls out one by one.

Write tally_summary(tally) that returns a dictionary with

• "n": the number of rolls,
• "mean": the mean result, as a float,
• "median": the middle result once all rolls are sorted, or the mean of the two middle results when n is even,
• "modes": the list of results with the highest count, in increasing order,
• "range": the largest result minus the smallest.

Results listed with a count of 0 never came up and must not affect any of these. If the tally holds no rolls at all, return {"n": 0, "mean": None, "median": None, "modes": [], "range": None}.

Examples

Input:  tally = {3: 2, -1: 1, 5: 4, 10: 0}
Output: {"n": 7, "mean": 3.5714285714285716, "median": 5, "modes": [5], "range": 6}
Explanation: the rolls are -1, 3, 3, 5, 5, 5, 5; the fourth one is 5; 10 never came up,
so the range is 5 - (-1) = 6.

Input:  tally = {1: 3000000000, 2: 1000000000, 6: 2000000000}
Output: {"n": 6000000000, "mean": 2.8333333333333335, "median": 1.5, "modes": [1], "range": 5}
Explanation: the two middle rolls are the 3000000000th (a 1) and the next one (a 2).

Constraints

• 0 <= len(tally) <= 10**5, keys are whole numbers with -10**9 <= result <= 10**9
• 0 <= count <= 10**12
• numbers are compared with a small tolerance; a whole-number median may be an int or a float

Goals

• Compute the mean, median, modes and range straight from a frequency table
• Find the middle positions with cumulative counts instead of expanding the data
• Ignore values that appear in the table with a count of zero