#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

struct Median {
    int value;
    //int index;
};

int main() {
    ifstream fin ("input.txt");
    ofstream fout ("output.txt");
    int n;
    fin >> n;
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;

    int a;
    Median median;
    median.value = 0;

    for (int i = 0; i < n; i++)
    {
        fin >> a;
        //choosing
        if (a < median.value)
        {
            max_heap.push(a);
        }
        else
        {
            min_heap.push(a);
        }

        //balancing
        int abs_ = max_heap.size() - min_heap.size();
        if (abs(abs_) > 1)
        {
            if (max_heap.size() > min_heap.size())
            {
                int tmp = max_heap.top();
                max_heap.pop();
                min_heap.push(tmp);
            } else
            {
                int tmp = min_heap.top();
                min_heap.pop();
                max_heap.push(tmp);
            }
        }

        //output
        if (max_heap.empty())
        {
            fout << min_heap.top() << ' ';
            median.value = min_heap.top();
        }
        else if (min_heap.empty())
        {
            fout << max_heap.top() << ' ';
            median.value = max_heap.top();
        }
        else if (min_heap.top() > max_heap.top())
        {
            fout << max_heap.top() << ' ';
            median.value = min_heap.top();
        }
        else
        {
            fout << min_heap.top() << ' ';
            median.value = max_heap.top();
        }
    }

    fin.close();
    fout.close();
    return 0;
}