class Solution {

    void removeOnly1(multiset<int> &ms, int v)

    {

        auto pr = ms.equal_range(v);

        ms.erase(pr.first);

    }

    void remove(multiset<int> &lmax, multiset<int> &rmin, int v)

    {

        if(v <= *lmax.rbegin())

        {

            removeOnly1(lmax, v);

            if(lmax.size() < rmin.size())

            {

                int tmp = *rmin.begin();

                lmax.insert(tmp);

                removeOnly1(rmin, tmp);

            }

        }

        else if(v >= *rmin.begin())

        {

            removeOnly1(rmin, v);

            if((lmax.size() - rmin.size()) > )

            {

                int tmp = *lmax.rbegin();

                removeOnly1(lmax, tmp);

                rmin.insert(tmp);

            }

        }

    }

    void addin(multiset<int> &lmax, multiset<int> &rmin, int v)

    {

        if(lmax.empty())

        {

            lmax.insert(v);

            return;

        }

        int lmax_v = *lmax.rbegin();

        int size_l = lmax.size(), size_r = rmin.size();

        if(v <= lmax_v) // to add left

        {

            lmax.insert(v);

            if((size_l +  - size_r) > )

            {

                int tmp = *lmax.rbegin();

                rmin.insert(tmp);

                removeOnly1(lmax, tmp);

            }

        }

        else

        {

            rmin.insert(v);

            if((size_r  + )> size_l)

            {

                int tmp = *rmin.begin();

                removeOnly1(rmin, tmp);

                lmax.insert(tmp);

            }

        }

    }

public:

    /**

     * @param nums: A list of integers.

     * @return: The median of the element inside the window at each moving

     */

    vector<int> medianSlidingWindow(vector<int> &nums, int k) {

        vector<int> ret;

        multiset<int> lmax, rmin; // sizeof(lmax) - sizeof(rmin) -> [0,1]

        size_t n = nums.size();

        for(int i = ; i < n; i ++)

        {

            if(i >= k)

            {

                remove(lmax, rmin, nums[i - k]);

            }

            //

            addin(lmax, rmin, nums[i]);

            //

            if(i >= k - )

            {

                ret.push_back(*lmax.rbegin());

            }

        }

        return ret;

    }

};