O(n log^2 n) solution using a Fenwick tree for the problem of the "running medians": given an array a[0..n), find the median of the subarrays a[0..0], a[0..1], a[0..2] and so on up to a[0..n-1] and then find the average of all these medians. Constraints: 1 <= n <= 10^6 and 0 <= a[i] <= 10^9.

gistfile1.cpp

// Andrés Mejía
using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

////////////// Prewritten code follows. Look down for solution. ////////////////
#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << (x) << endl

const double EPS = 1e-9;
int cmp(double x, double y = 0, double tol = EPS) {
    return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
}
////////////////////////// Solution starts below. //////////////////////////////

const int MAXN = 1e6 + 5;

namespace Fenwick {
    int tree[MAXN];
    
    void clear() {
        memset(tree, 0, sizeof tree);
    }
    
    void add(int at, int what) {
        for (at++; at < MAXN; at += at & -at) {
            tree[at] += what;
        }
    }
    
    int get(int at) {
        int ans = 0;
        for (at++; at > 0; at -= at & -at) {
            ans += tree[at];
        }
        return ans;
    }
}

// The input.
int a[MAXN];

int main(){
    int n;
    while (cin >> n) {
        if (n == 0) break;
        
        Fenwick::clear();
        vector<int> sorted;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            sorted.push_back(a[i]);
        }
        sort(sorted.begin(), sorted.end());
        sorted.resize(unique(sorted.begin(), sorted.end()) - sorted.begin());
        // compress
        for (int i = 0; i < n; ++i) a[i] = lower_bound(sorted.begin(), sorted.end(), a[i]) - sorted.begin();
        
        long long sum = 0;
        // now sweep from left to right
        for (int i = 0; i < n; ++i) {
            Fenwick::add(a[i], +1);

            // Binary search for the median
            int low = 0, high = n - 1;
            int k = i / 2; // this is the 0-index of the median of the elements a[0..i] if they were all sorted.
            while (low < high) {
                int mid = (low + high) / 2;
                
                if (Fenwick::get(mid) >= k + 1) { // either mid is the median, or it's smaller.
                    high = mid;
                } else { // the median is definitely bigger than mid.
                    low = mid + 1;
                }
            }
            assert(low == high);
            // low is the compressed median
            assert(Fenwick::get(low) >= k + 1 and (low == 0 or Fenwick::get(low - 1) < k + 1));
            
            int actual_median = sorted[low];

            sum += actual_median;
        }
        printf("%.2lf\n", 1.0 * sum / n);
        
    }
    return 0;
}