如果一个整数序列 $a_1, a_2, \dots, a_n$ 满足 $m_1 \le m_2 \le \dots \le m_n$，其中 $m_i$ 是序列 $a_1, a_2, \dots, a_i$ 的中位数，则称该序列是“好的”（good）。

给定一个序列 $p_1, p_2, \dots, p_n$，请找到它的一个排列，使得该排列是“好的”。如果存在多个满足条件的排列，请输出字典序最大的那一个。

对于序列 $a_1, a_2, \dots, a_n$，其中位数的定义为：若 $n$ 为奇数，则为第 $\lceil n/2 \rceil$ 大的元素；若 $n$ 为偶数，则为第 $n/2$ 大的元素与第 $(n/2 + 1)$ 大的元素的平均值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^9$)。

输出格式

第一行输出 $n$ 个整数，表示输入序列中字典序最大的“好的”排列。

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

1 3 2 5 4

样例输入 2

8
1 2 2 3 3 3 4 4

样例输出 2

3 3 4 3 4 2 2 1