从前，有一个小青蛙决定去荷叶上练习跳跃。 现在有n个荷叶排成一排，小青蛙一开始在最左边的荷叶（一号荷叶）上。这只青蛙很厉害，可以在任意两个荷叶之间跳跃。 有一天它突发奇想，想用一种奇怪的方式完成跳跃练习：

1. 它希望每次跳到不同的荷叶上；

2. 每一次跳的距离不同。 请给出1到n这n个自然数的一个排列 (a_{1} , a_{2}, ...., a_{n} )，使得：

   i. a_{1} = 1 ；

   ii. 对于任意的 i ≠ j(1 ≤ i,j ≤ n-1)，有 |a_{i} - a_{i+1}| ≠ |a_{j} - a_{j+1}|。

一行一个整数 n。

一行 n 个数，空格分隔，末尾无多余空格。

数据范围

对于20%的数据：1 < n ≤ 4;

对于100%的数据：1 < n ≤ 10000;

另:|a_{i} - a_{i+1}| ≠ |a_{j} - a_{j+1}|即表示每次跳的距离要不一样不能重复，且只能从1-n之间选择。

Oiclass

递推