中位数

#include <cstdio>
#include <queue>
using namespace std;

/*
首先，程序提示用户输入一个整数n，表示接下来要输入的整数的数量。
接着，程序创建两个优先队列：q1和q2。q1是一个最小堆，用于存储较小的元素；q2是一个最大堆，用于存储较大的元素。
程序进入一个循环，循环n次。在每次循环中，程序提示用户输入一个整数x。
根据x的大小，程序决定将x添加到哪个优先队列中：
如果q2为空，或者x大于等于q2的顶部元素（即q2中的最大元素），则将x添加到q2中。
否则，将x添加到q1中。
每次添加新元素后，程序检查两个优先队列的大小，以确保q1中的所有元素都小于q2中的所有元素。如果q2的大小超过q1的大小加1，程序将q2的顶部元素（最大元素）移动到q1中。如果q1的大小超过q2的大小加1，程序将q1的顶部元素（最小元素）移动到q2中。
在循环的奇数次迭代中，程序输出q1的顶部元素；在偶数次迭代中，输出q2的顶部元素。这样可以确保输出的序列是交替的，且每次输出的都是当前两个堆中较大的元素。
循环结束后，程序结束。
*/

int main() {
    int n;
    scanf("%d", &n);  // 读取输入的整数n

    priority_queue<int> q1;  // 创建一个优先队列q1，用于存储较小的元素
    priority_queue<int, vector<int>, greater<int> > q2;  // 创建一个优先队列q2，用于存储较大的元素

    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);  // 读取输入的整数x

        // 如果q2为空或者x大于等于q2的顶部元素，将x添加到q2中
        if (q2.empty() || x >= q2.top()) {
            q2.push(x);
            // 如果q2的大小大于q1的大小加1，将q2的顶部元素弹出并添加到q1中
            if (q2.size() > q1.size() + 1) {
                int t = q2.top();
                q2.pop();
                q1.push(t);
            }
        }
        else {
            // 否则，将x添加到q1中
            q1.push(x);
            // 如果q1的大小大于q2的大小加1，将q1的顶部元素弹出并添加到q2中
            if (q1.size() > q2.size() + 1) {
                int t = q1.top();
                q1.pop();
                q2.push(t);
            }
        }

        // 如果i是奇数，输出q1或q2的顶部元素（取决于哪个队列的大小更大）
        if (i % 2 == 1) {
            if (q1.size() > q2.size())
                printf("%d\n", q1.top());
            else
                printf("%d\n", q2.top());
        }
    }

    return 0;
}