vector<double> runningMedian(vector<int> a) {
    priority_queue<int> lowers; //max heap
    priority_queue<int, vector<int>, greater<int>> highers; //min heap
    vector<double> result;
    int n = a.size();
    int number;
    

    lowers.push(a[0]);
    result.push_back((double)a[0]);

    for(int i = 1; i < n; i++){
        number = a[i];

        // adding numbers
        if(number < lowers.top()){
            lowers.push(number);
        } else {
            highers.push(number);
        }

        // rebalancing the heaps

        int l = lowers.size();
        int h = highers.size();
        if((l - h) > 1){
            highers.push(lowers.top());
            lowers.pop();
        } 

        if((h - l) > 1){
            lowers.push(highers.top());
            highers.pop();
        }


        // finding median
        if(i%2 == 1){
            int aa = lowers.top() + highers.top();
            result.push_back(((double)aa)/2);
        } else {
            if(l > h){
                result.push_back(lowers.top());
            } else {
       
                result.push_back(highers.top());
            }
        }

        
    }

    return result;

}