C. Construct A Permutation
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$p$$$ is a permutation with length $$$n$$$, and $$$p_i$$$ denotes the $$$i$$$-th element of $$$p$$$.

find a permutation of length $$$n$$$ that this permutation has the maximum value of

$$$$$$|||...||p_1-p_2|-p_3|...|-p_{n-1}|-p_n|$$$$$$

among all possible permutations with length $$$n$$$.

Input

the input contains only one integer $$$n$$$ $$$(1\le n \le 10^6)$$$.

Output

output $$$n$$$ integers, denoting the answer. if there are multiple answers, output any.

Examples
Input
1
Output
1
Input
2
Output
1 2
Input
6
Output
4 3 5 2 1 6
Input
15
Output
13 2 10 3 1 12 8 4 5 9 7 6 15 11 14
Note

A permutation of length $$$n$$$ is an array of length $$$n$$$, and each integer from $$$1$$$ to $$$n$$$ appears exactly once in that array. for example, $$$[1,3,4,2]$$$, $$$[1]$$$, $$$[4,3,2,1,5]$$$ are permutations while $$$[1,1,4,5,1,4]$$$, $$$[2]$$$, $$$[1,-2]$$$ are not.