#P1845. 2024.7.20-KDXF-第一题-序列中位数提取

2024.7.20-KDXF-第一题-序列中位数提取

问题描述

给定一个长度为 nn 的正整数序列，请按照以下规则依次提取序列的中位数并输出：

  1. 如果序列的大小为奇数，则中位数是按照升序排序后中间的数字。
  2. 如果序列的大小为偶数：
    • 如果排序后中间的两个数字 xx 和 yy 相等，输出任意一个即可。
    • 如果排序后中间的两个数字 xx 和 yy 不相等，输出较小的那个数字。

每次输出中位数后，该中位数从序列中删除，并重复上述步骤，直至序列为空。

输入描述

第一行输入一个正整数 nn，表示序列的长度（1≤n≤1051 \leq n \leq 10^5）。

第二行输入 nn 个正整数，表示序列的元素（1≤ai≤1091 \leq a_i \leq 10^9）。

输出描述

一行输出 nn 个整数，表示依次提取出的中位数。

样例输入

4
1 8 9 5

样例输出

5 8 1 9

样例输入

6
6 6 6 6 6 6

样例输出

6 6 6 6 6 6

知识点:*****

查看知识点以及同类型题目

Statistics