running_mean.py

#!/usr/bin/env python3

from heapq import heappush, heappop

median = None

heap_lower = []
heap_upper = []

len_lower = 0
len_upper = 0


def next_num(x):
    global median
    global len_lower
    global len_upper

    if median is None:
        len_lower = 1
        heappush(heap_lower, -x)
        median = x
        return median

    if x <= median:
        len_lower += 1
        heappush(heap_lower, -x)
        if len_lower > len_upper + 1:
            tmp = -heappop(heap_lower)
            heappush(heap_upper, tmp)
            len_lower -= 1
            len_upper += 1
    else:
        len_upper += 1
        heappush(heap_upper, x)
        if len_upper > len_lower:
            tmp = heappop(heap_upper)
            heappush(heap_lower, -tmp)
            len_upper -= 1
            len_lower += 1

    if len_lower == len_upper:
        l = -heap_lower[0]
        h = heap_upper[0]
        median = (l + h) / 2
    else:
        median = -heap_lower[0]

    return median


if __name__ == '__main__':
    n = int(input())
    for _ in range(n):
        x = int(input())
        print(next_num(x))