백준_1655

#include <iostream>
#include <queue>

#define endl "\n"
#define Max 100000
using namespace std;

int n;
int Arr[Max];
//n은 1~100,000, 정수는 -10,000~10,000

void Input() {
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> Arr[i];
}

void Solution() {
	priority_queue<int> Max_PQ, Min_PQ;
	
	for (int i = 0; i < n; i++) {
		if (Max_PQ.size() > Min_PQ.size())
			Min_PQ.push(-Arr[i]);
		else Max_PQ.push(Arr[i]);

		if (Max_PQ.empty() == false && Min_PQ.empty() == false) {
			if (Max_PQ.top() > -Min_PQ.top()) {
				int Max_Value  = Max_PQ.top();
				int Min_Value  = -Min_PQ.top();

				Max_PQ.pop();
				Min_PQ.pop();

				Max_PQ.push(Min_Value);
				Min_PQ.push(-Max_Value);
			}
		}
		cout << Max_PQ.top() << endl;
	}
}

void Solve() {
	Input();
	Solution();
}

int main(void)
{
	ios::sync_with_stdio(false); //속도 증가
	cin.tie(NULL);
	cout.tie(NULL);

	Solve();

	return 0;
}

성공, 복습 필요.!