国际象棋俱乐部正在组织一场国际象棋表演赛。俱乐部有 $n$ 名国际象棋选手，编号从 $1$ 到 $n$，其中第 $i$ 名选手的等级分（rating）为 $r_i$。在表演赛中，将有 $2k$ 名选手参加，他们将被分成 $k$ 对，并同时进行 $k$ 场比赛。为了让表演赛更加精彩，俱乐部希望将每一对选手中两人的等级分差的最大值降到最低。

你的任务是对于每一个从 $1$ 到 $\lfloor \frac{n}{2} \rfloor$ 的 $k$，计算如果俱乐部最优地选择 $2k$ 名选手并将他们配对，所能达到的最小等级分差最大值。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)，表示国际象棋选手的数量。

第二行包含 $n$ 个整数，其中第 $i$ 个整数为 $r_i$ ($1 \le r_i \le 10^{18}$)，表示第 $i$ 名选手的等级分。

输出格式

在唯一的一行输出中，应包含 $\lfloor \frac{n}{2} \rfloor$ 个整数。第 $k$ 个整数表示如果俱乐部想要组成 $k$ 对选手，所求的结果。

样例

输入 1

6
100 13 20 14 10 105

输出 1

1 5 6

说明

对于 $k=1$，我们需要将编号为 $2$ 和 $4$ 的选手配对。

对于 $k=2$，我们可以例如组成以下配对：$(4, 5)$ 和 $(1, 6)$。

对于 $k=3$，我们需要组成以下配对：$(1, 6)$、$(2, 5)$ 和 $(3, 4)$。