#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>

using namespace std;

int N;
priority_queue<int, vector<int>, less<int>> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;

void Input() {
	cin >> N;
}

void Solve() {
	// N 번동안 숫자 받기
	for (int i = 0; i < N; i++) {
		int num; // 숫자
		cin >> num; // 숫자 받기

		// max 큐 크기가 min 큐 크기 보다 크면, min에, 아니면 max에 값 넣기 (top에 중앙을 유지하기 위해)
		if (max_pq.size() > min_pq.size()) min_pq.push(num);
		else max_pq.push(num);

		// max 큐와 min 큐의 크기가 같고, 둘다 비어있지 않은 경우
		if (max_pq.empty() == false && min_pq.empty() == false) {
			// max_pq의 크기가 더 크면 min과 swap
				// 더 작은 값을 출력해 줘야하기 때문 (짝수의 경우)
			if (max_pq.top() > min_pq.top()) {
				int temp_max = max_pq.top();
				max_pq.pop();
				int temp_min = min_pq.top();
				min_pq.pop();

				max_pq.push(temp_min);
				min_pq.push(temp_max);
			}
		}
		cout << max_pq.top() << "\n";
	}
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//1. 입력
	Input();

	//2. 풀이
	Solve();

	return 0;
}