#include <bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int> > q1; // 大根堆
priority_queue<int, vector<int>, greater<int> > q2; // 小根堆
inline int myabs(int x) { return x > 0 ? x : -x; } // 绝对值函数

int main()
{
    int n; scanf("%d", &n); // 读入n
    int x; scanf("%d", &x); // 读入第一个数
    q1.push(x); // 将第一个数放入大根堆
    printf("%d\n", x);
    for (int i = 2, x; i <= n; i++)
    {
        scanf("%d", &x); // 读入第i个数
        if (x > q1.top()) q2.push(x);
        else q1.push(x);

        while (myabs(q1.size() - q2.size()) > 1)
            if (q1.size() > q2.size()) { q2.push(q1.top()); q1.pop(); }
            else { q1.push(q2.top()); q2.pop(); }

        if (i % 2)
        {
            if (q1.size() > q2.size()) printf("%d\n", q1.top()); else printf("%d\n", q2.top());
        }
    }
    return 0;
}