A permutation of integers 1,2,…,n is called beautiful if there are no adjacent elements whose difference is 111.

Given nnn, construct a beautiful permutation if such a permutation exists.

Input

The only input line contains an integer on n.

Output

Print a beautiful permutation of integers 1,2,…,n. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

Constraints

• 1 <= n <= 10^6

Example-1

Input:

5

Output:

4 2 5 3 1

Solution

Let's analyze the first example, we can see that we have the sequence (4,2,5,3,1), and the difference between the two consecutive numbers is 2, and hence, we can see that this is a valid sequence while other sequences like (1,2,3,4,5) or (5,4,3,2,1) are not valid and hence is the answer.

To solve this problem we just need to make sure that consecutive integers do not have a difference of more than 1 and hence we can simply think of printing 1,3,2,5,4 as a valid sequence.

So, to solve this problem, we need to print alternate odd-even numbers, and we have to handle the edge cases such as when N = 2,3 we can see that in these cases we do not have a valid sequence so we print "NO SOLUTION".

Also for N = 1, we do not have any valid sequence so we print 1.

Also for N = 4, the sequence, we do not have a valid sequence so we print "2 4 1 3"

Hence, we print NO SOLUTION for this sequence.

Let's code the solution up.

#include<bits/stdc++.h>
using namespace std;

int main(){
     int n;
     cin >> n;
     if(n == 1){
          cout << 1;
     }
     else if(n <= 3){
          cout << "NO SOLUTION";
     }else{
           for(int i=1;i<=n;i+=2)
                     cout << i << " ";

            for(int i=2;i<=n;i+=2)
                     cout << i << " ";

     }
}

So, in this fashion, we need to work to cover the test cases.

That's all for this, will see you soon.