# Appreciation

/*
 * Problem :: 1655 / 가운데를 말해요
 *
 * Kind :: Data Structure
 *
 * Insight
 * - 숫자 넣을 때마다 정렬해줄까?
 *   O(N * NlogN) => 시간초과
 *   + Tree 를 어떻게 직접 잘 만들어서
 *     중간의 숫자가 root 가 되게끔 할 수 있나?
 *     # Balanced Tree... 거의 AVL Tree 만드는 수준이잖아...
 *       (학교에서 Java 로 직접 만들었던 악몽이 떠오른다 ㅠㅠ)
 *   + 시간복잡도가 작고 자동으로 정렬해주는 자료구조 중에 쓸만한게 있나?
 *     Heap, Map
 *     중간의 숫자만 말하는 거니까 Map 보다는
 *     아무래도 MinHeap, MaxHeap 이 사용되는게 나을 듯 싶다
 *
 * - 지금 들어가야하는 숫자 n 과 현재 중간의 숫자 m 이 있고
 *   n 을 넣었을 때 m 근처의 숫자들을 효과적으로 다루어서 중간의 숫자들을 찾으려면...
 *   m 보다 같거나 작은 숫자중 최댓값과
 *   m 보다 큰 숫자중 최솟값을 항상 추적하고 있어야 한다
 *   또한 현재 m 보다 같거나 작은 숫자의 개수와
 *   m 보다 큰 숫자의 개수를 항상 알고 있어야 한다
 *   + m 보다 같거나 작은 숫자중 최댓값 및 개수 추적 => MaxHeap
 *     m 보다 큰 숫자중 최솟값 및 개수 추적 => MinHeap
 *     # MaxHeap 과 MinHeap 을 연결시키고
 *       MaxHeap.top() 을 항상 중간의 숫자로 만들 수 있을 것 같다!
 *
 * Point
 * - MaxHeap.top() 이 항상 중간의 숫자임을 보장하도록 만들어야 한다
 *   + 이를 위해선, MaxHeap.size() 는 항상 MinHeap.size() 보다 같거나 1 더 크게 유지시켜준다
 *     이렇게 하면, MaxHeap.top() 보다 같거나 낮은 숫자들은 MaxHeap 에 있고
 *     MaxHeap.top() 보다 큰 숫자들은 MinHeap 에 있게된다
 *     # [1, 2, 3] [4, 5]
 *       [1, 2, 3] - MaxHeap
 *       [4, 5] - MinHeap
 *       중간의 숫 - 3
 *     # [-99, 1, 2, 5] [5, 7, 10] (예제 입력 1)
 *       [-99, 1, 2, 5] - MaxHeap
 *       [5, 7, 10] - MinHeap
 *       중간 숫자 - 5
 *       -> 여기에 3을 추가한다고 하면
 *         현재 중간의 숫자보다 작으니 MaxHeap 에 추가한다
 *         그런데 이러면 MaxHeap 이 MinHeap 보다 2개의 원소를 더 갖게 된다
 *         이러면 MaxHeap.top() 이 중간의 숫자라는 보장이 깨지므로
 *         MaxHeap.top() 을 빼서 MinHeap 에 넣어준다
 *         그럼 다음과 같이 된다
 *         [-99, 1, 2, 3] - MaxHeap
 *         [5, 5, 7, 10] - MinHeap
 *         이 경우, 중간의 숫자가 3이 됨을 알 수 있다
 *       -> 여기에 11을 추가한다고 하면
 *         현재 중간의 숫자보다 크니 MinHeap 에 추가한다
 *         그런데 이러면 MinHeap 이 MaxHeap 보다 1개의 원소를 더 갖게 된다
 *         이러면 MaxHeap.top() 이 중간의 숫자라는 보장이 깨지므로
 *         MinHeap.top() 을 빼서 MaxHeap 에 넣어준다
 *         그럼 다음과 같이 된다
 *         [-99, 1, 2, 3, 5] - MaxHeap
 *         [5, 7, 10, 11] - MinHeap
 *         이 경우, 중간의 숫자가 5가 됨을 알 수 있다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <queue>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;

    // Process
    priority_queue<int> low; /* MaxHeap */
    priority_queue<int, vector<int>, greater<>> high; /* MinHeap */

    for (int i=0; i<N; i++) {
        int n; cin >> n; /* 현재 들어가야 하는 숫자 */

        /* MaxHeap 이 비어있거나, 현재 들어가야 하는 숫자가 중간 숫자보다 같거나 작으면
         * MaxHeap 에 넣고, 그렇지 않으면 MinHeap 에 넣음 */
        (low.empty() || n <= low.top()) ? low.push(n) : high.push(n);

        /* MaxHeap 의 원소의 개수가 MinHeap 의 원소의 개수+1 보다 큰 경우, 보정해줌 */
        if (low.size() > high.size()+1) {
            high.push(low.top());
            low.pop();
        } /* 숫자는 한개씩 추가되고, 그때마다 이상이 있으면 보정하므로
           * max(MaxHeap.size() - MinHeap.size()) 는 2이다
           * 보정하면, MaxHeap.size() 와 MinHeap.size() 는 같게 됨
           * => while 문을 안쓰는 이유 */

        /* MinHeap 의 원소의 개수가 MaxHeap 의 원소의 개수보다 큰 경우, 보정해줌 */
        if (high.size() > low.size()) {
            low.push(high.top());
            high.pop();
        } /* 숫자는 한개씩 추가되고, 그때마다 이상이 있으면 보정하므로
           * max(MinHeap.size() - MaxHeap.size()) 는 1이다
           * 보정하면, MaxHeap.size() 는 MinHeap.size()+1 과 같게 됨
           * => while 문을 안 쓰는 이유 */

        // Control : Output
        cout << low.top() << endl;
    }
}

// Helper Functions
/* None */