Hello everyone. Here is problem I recently encountered on 'Algorithm and data structures' course exam. The problem statement is:

You are given a sequence a1,a2,...,an, and a number b. Your task is to find algorithm which counts all pairs (l,r) such that median of sequence a(l),a(l+1),..,a(r) is bigger than b.

My solution on exam was O(n^2logn) which used order statistics tree. Other solutions were

• O(n^2) — used sorting to check median of pair in constant time

• O(nlogn) — related to counting inverses in permutation.

And surprisingly someone came up with O(n) solution. So here is my question, can anyone tell me about this solution to the problem? I'm quite curious how this can be done in linear time.