该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

约翰有N 头奶牛，由 1 到 N 编号.每天晚上，奶牛们按照比较任意的顺序站成一队等待吃饭.这样，任何一种站队的方式都可以表示为一个长度为 N 位的 N 进制数.

约翰不喜欢奶牛们乱糟糟的顺序.他希望奶牛们站队顺序所对应的那个 N 进制数越小越好.当然，奶牛们很不愿意每次排队都站在同一个位置，那很无聊.

于是，约翰和奶牛们签订了一份协议:每天晚上吃饭前，奶牛们按照自己的喜好随便站成一队，然后约翰可以做出某些调整.调整的规定是:在同一个位置上调整之前的奶牛的编号与调整后奶牛的编号之差的绝对值不允许超过 1. 比如 8 头奶牛一开始这样站:

8, 5, 7, 3, 6, 4, 2, 1.

约翰就会把它调整为:

7 . 4. 8. 2. 6. 5. 3, 1.

这是在协议之下所能达到的最小的 N 进制数.但是，随着奶牛日益增多，约翰已经无法应付如此繁重的计算.你的任务就是找出最优(最小的顺序，使得约翰能够方便地调整奶牛们的位置）

Format

Input

第 1 行:1 个整数 N(3 <= N <= 50000);

第 2 到 N+l 行:每行 1 个整数，从前往后表示调整之前奶牛的排队顺 序.

Output

一共 N 行，表示调整之后的奶牛的排队顺序.

Samples

8
8
5
7
3
6
4
2
1

7
4
8
2
6
5
3
1