Streaming exercise

Here is an (HW?) exercise in streaming algorithm design.

Given a stream of items a_1,...,a_n, a_i \in [1,u], find the average of items below the median or the median of items below the average.

There is previous work on finding the median (or more generally, the quantiles) and the kth frequency moments \sum_i f_i^k, where f_i is the frequency of i (k=1 is the average). The exercise here is an example of cascaded aggregation: computing the kth frequency moment following a quantile computation.

As is standard in streaming algorithms, one has to use space and per-item update time of polylog(n,u) and obtain reasonable approximation.