有一节车厢，里头共有 $n$ 个座位摆成一排，从左至右分别编号为 $1, 2, \dots, n$。 有 $n$ 位分别编号为 $1, 2, \dots, n$ 的乘客，将按照编号顺序从小到大**依次**进入这节车厢，并挑选一个空的座位坐下。在上一位乘客挑选完座位并坐下之后，下一位乘客才会进入车厢。 但，这 $n$ 位乘客都是社恐！他们每次挑选座位时，都会优先选择那些离**先前已经坐下的乘客**的**最短距离更远**的座位。如果存在多个符合条件的空座位，他们会优先选择**编号更小**的座位。 我们定义两位乘客的距离为**他们挑选的座位编号之差的绝对值**。 请你帮忙求出，在 $n$ 名乘客都进入车厢都坐下之后，每个座位上的乘客编号分别是多少？

一个正整数 $n$，表示座位以及乘客的数量。 - $1 \le n \le 100\,000$

$n$ 个正整数，第 $i$ 个正整数表示坐在编号为 $i$ 的座位上的乘客编号，整数间以单个空格隔开。

***对于样例：*** - 第一位乘客进入车厢，此时所有座位均为空，他会选择编号为 $1$ 的座位坐下，座位占用情况为 $\{1,/,/,/,/,/,/,/\}$； - 第二位乘客进入车厢，每个座位与已坐下的乘客之间的最短距离分别为 $\{/,1,2,3,4,5,6,7\}$，他会选择编号为 $8$ 的座位坐下，座位占用情况为 $\{1,/,/,/,/,/,/,2\}$； - 第三位乘客进入车厢，每个座位与已坐下的乘客之间的最短距离分别为 $\{/,1,2,3,3,2,1,/\}$，发现编号为 $4$ 与编号为 $5$ 的座位均满足最短距离最远的条件，他会选择编号为 $4$ 的座位坐下，座位占用情况为 $\{1,/,/,3,/,/,/,2\}$； - 第四位乘客进入车厢，每个座位与已坐下的乘客之间的最短距离分别为 $\{/,1,1,/,1,2,1,/\}$，他会选择编号为 $6$ 的座位坐下，座位占用情况为 $\{1,/,/,3,/,4,/,2\}$； - 此时每个座位与已坐下的乘客之间的最短距离分别为 $\{/,1,1,/,1,/,1,/\}$，后面进来的四位乘客将会分别选择 $2,3,5,7$ 这四个座位坐下，最终的座位占用情况为 $\{1,5,6,3,7,4,8,2\}$。