#include <bits/stdc++.h>
#define int long long
#define inf LONG_LONG_MAX
using namespace std;
const int maxn = 100005;
struct treenode {
	int val, lc, rc, cnt, siz;
} tree[maxn];
int tsiz;

void insert(int x, int u) {
	tree[u].siz++;

	if (tree[u].val == x)
		tree[u].cnt++;

	if (tree[u].val < x) {
		if (tree[u].rc) {
			insert(x, tree[u].rc);
		} else {
			tree[++tsiz].val = x;
			tree[u].rc = tsiz;
			tree[tsiz].cnt = tree[tsiz].siz = 1;
		}
	} else {
		if (tree[u].lc) {
			insert(x, tree[u].lc);
		} else {
			tree[++tsiz].val = x;
			tree[u].lc = tsiz;
			tree[tsiz].cnt = tree[tsiz].siz = 1;
		}
	}
}

inline int qv(int rk, int u) {
	if (!u)
		return 0;

	if (rk == 0)
		return 0;

	if (tree[tree[u].lc].siz >= rk) {
		return qv(rk, tree[u].lc);
	} else if (tree[tree[u].lc].siz + tree[u].cnt >= rk) {
		return tree[u].val;
	} else {
		return qv(rk - tree[tree[u].lc].siz - tree[u].cnt, tree[u].rc);
	}
}

signed main() {
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		if (!tsiz) {
			tree[++tsiz].val = x;
			tree[tsiz].cnt = tree[tsiz].cnt = 1;
		} else {
			insert(x, 1);
		}
		if (i % 2) {
			cout << qv(i / 2 + 1, 1) << endl;
		}
	}
	return 0;
}

rt