#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 5;
int n, root, cnt;
struct tr {
    int fa, son[2], siz, num, val;
}tr[MAXN];
int a[MAXN];
void init()
{
    tr[root].fa = 0;
    tr[root].son[0] = tr[root].son[1] = tr[root].siz = tr[root].num = 0;
    root = 0;
}
int New(int val, int fa)
{
    cnt++;
    tr[cnt].fa = fa;
    tr[cnt].val = val;
    tr[cnt].num = tr[cnt].siz = 1;
    return cnt;
}

void Delete(int x)
{
    tr[x].fa = 0;
    tr[x].son[0] = tr[x].son[1] = tr[x].siz = tr[x].num = 0;
}

void update(int x)
{
    if (!x)return;
    tr[x].siz = tr[x].num;
    if (tr[x].son[0])
    {
        tr[x].siz += tr[tr[x].son[0]].siz;
    }
    if (tr[x].son[1])
    {
        tr[x].siz += tr[tr[x].son[1]].siz;
    }
}
void rotate(int x)
{
    int y = tr[x].fa;
    int z = tr[y].fa;
    int c = (tr[y].son[0] == x);

    tr[y].son[!c] = tr[x].son[c];
    tr[tr[x].son[c]].fa = y;
    tr[x].fa = z;
    if (z)
    {
        tr[z].son[tr[z].son[1] == y] = x;
    }

    tr[x].son[c] = y;
    tr[y].fa = x;
    update(y);
    update(x);
}

void splay(int x, int goal)
{
    while (tr[x].fa != goal)
    {
        int y = tr[x].fa, z = tr[y].fa;

        if (z != goal)
        {
            ((tr[z].son[0] == y) ^ (tr[y].son[0] == x)) ? rotate(x) : rotate(y);
        }
        rotate(x);
    }

    if (!goal)
    {
        root = x;
    }
}

bool find(int val)
{
    int x = root;
    while (1)
    {
        if (tr[x].val == val)
        {
            splay(x, 0);
            return 1;
        }

        if (tr[x].son[tr[x].val < val])
        {
            x = tr[x].son[tr[x].val < val];
        }
        else
        {
            splay(x, 0);
            return 0;
        }
    }
}

int pre()
{
    int x = tr[root].son[0];
    while (tr[x].son[1])
    {
        x = tr[x].son[1];
    }
    return x;
}

int nxt()
{
    int x = tr[root].son[1];
    while (tr[x].son[0])
    {
        x = tr[x].son[0];
    }
    return x;
}

void insert(int val)
{
    if (!root)
    {
        root = New(val, 0);
        return;
    }

    if (find(val))
    {
        tr[root].num++;
        tr[root].siz++;
        return;
    }

    int x = root;
    while (1)
    {
        if (tr[x].son[tr[x].val < val])
        {
            x = tr[x].son[tr[x].val < val];
        }
        else
        {
            tr[x].son[tr[x].val < val] = New(val, x);
            update(x);
            splay(tr[x].son[tr[x].val < val], 0);
            return;
        }
    }
}
void del(int val)
{
    find(val);
    int x = root;
    tr[root].num--;
    tr[root].siz--;
    if (tr[root].num) return;
    if (!tr[root].son[0] and !tr[root].son[1])
    {
        init();
        return;
    }

    if (!tr[root].son[0])
    {
        root = tr[root].son[1];
        tr[root].fa = 0;
        Delete(x);
        return;
    }
    if (!tr[root].son[1])
    {
        root = tr[root].son[0];
        tr[root].fa = 0;
        Delete(x);
        return;
    }

    find(tr[pre()].val);
    splay(x, root);
    if (tr[x].son[1])
    {
        tr[root].son[1] = tr[x].son[1];
        tr[tr[x].son[1]].fa = root;
    }

    Delete(x);
}

int getrk(int val)
{
    int x = root, res = 0;
    while (1)
    {
        if (val == tr[x].val)
        {
            res += tr[x].son[0] ? tr[tr[x].son[0]].siz + 1 : 1;
            splay(x, 0);
            return res;
        }

        if (val < tr[x].val)
        {
            if (!tr[x].son[0])
            {
                res++;
                return res;
            }
            x = tr[x].son[0];
        }
        else
        {
            res += tr[x].num;
            if (tr[x].son[0])
            {
                res += tr[tr[x].son[0]].siz;
            }

            if (!tr[x].son[1])
            {
                return res;
            }

            x = tr[x].son[1];
        }
    }
}
int getval(int tot)
{
    int x = root;
    while (1)
    {
        if (tr[x].son[0] and tot <= tr[tr[x].son[0]].siz)
        {
            x = tr[x].son[0];
        }
        else
        {
            tot -= tr[tr[x].son[0]].siz;
            if (tot <= tr[x].num)
            {
                return tr[x].val;
            }
            tot -= tr[x].num;
            x = tr[x].son[1];
        }
    }
}

void print(int p)
{
    if (p)
    {
        print(tr[p].son[0]);
        cout << tr[p].fa << " " << tr[p].siz << " " << tr[p].num << " " << tr[p].val << endl;
        print(tr[p].son[1]);
    }
}
long long result = 0;
int main()
{
    ios::sync_with_stdio(false);
    //freopen("book.in", "r", stdin);
    //freopen("book.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        insert(a[i]);
        if (i & 1) {
            int num = getval((i - 1) / 2 + 1);
            cout << num << '\n';
            //cout << getval(num) << endl;
        }
    }
    return 0;
}