# $O(n^2logn)$
TLE

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    vector<int> v;
    while(cin>>n)
    {
        v.push_back(n);
        if(v.size()==0)
        {
            cout<<n<<"\n";
            continue;
        }
        sort(v.begin(),v.end());
        int t=v.size()/2;
        if(v.size()%2==0)
            cout<<(v[t]+v[t-1])/2<<"\n";
        else
            cout<<v[t]<<"\n";
    }
}

# $O(n^2)$

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    vector<int> v;
    while(cin>>n)
    {
        if(v.size()==0)
        {
            v.push_back(n);
            cout<<n<<"\n";
            continue;
        }
        v.push_back(0);

        int i=v.size()-2;
        while(v[i]>n)
        {
            swap(v[i],v[i+1]);
            i--;
        }
        v[i+1]=n;

        int t=v.size()/2;
        if(v.size()%2==0)
            cout<<(v[t]+v[t-1])/2<<"\n";
        else
            cout<<v[t]<<"\n";
    }
}

# O(nlogn)
用heap維護兩端，左半為max heap，右半為min heap，使開口朝中間，當兩端大小幾乎一樣時，兩個top的平均就是中位數
[參考](https://alan23273850.github.io/Online-Judge-Problems/zerojudge/d713/)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    priority_queue<int> l;
    priority_queue<int,vector<int>,greater<int>> r;
    int n;
    l.push(INT_MIN),r.push(INT_MAX);
    while(cin>>n)
    {
        if(n<l.top())
        {
            if(l.size()>r.size())
            {
                r.push(l.top());
                l.pop();
            }
            l.push(n);
        }
        else if(n>r.top())
        {
            if(l.size()<r.size())
            {
                l.push(r.top());
                r.pop();
            }
            r.push(n);
        }
        else if(l.size()<r.size())
            l.push(n);
        else
            r.push(n);

        if(l.size()>r.size())
            cout<<l.top()<<endl;
        else if (l.size()<r.size())
            cout<<r.top()<<endl;
        else cout<<(l.top() + r.top())/2<<endl;
    }
}