2629. Cyclic antimonotonic permutations

单点时限: 5.0 sec

内存限制: 256 MB

A permutation is a sequence of integers which contains each integer from 1 to n exactly once. In this problem we are looking for permutations with special properties:

  1. Antimonotonic: for each consecutive 3 values pi-1, pi, pi+1 (1 < i < n), pi should either be the smallest or the biggest of the three values.

  2. Cyclic: The permutation should consist of only one cycle, that is, when we use pi as a pointer from i to pi, it should be possible to start at position 1 and follow the pointers and reach all n positions before returning to position 1.

输入格式

The input file contains several test cases. Each test case consists of a line containing an integer n, (3 ≤ n ≤ 106), the number of integers in the permutation. Input is terminated by n=0.

输出格式

For each test case print a permutation of the integers 1 to n which is both antimonotonic and cyclic. In case there are multiple solutions, you may print any one. Separate all integers by whitespace characters.

样例

Input
3
5
10
0
Output
3 1 2
4 5 2 3 1
6 10 2 9 3 5 4 7 1 8

1 人解决,6 人已尝试。

4 份提交通过,共有 15 份提交。

9.9 EMB 奖励。

创建: 11 年前.

修改: 2 年,11 月前.

最后提交: 8 年,11 月前.

来源: Ulm Local 2009

题目标签