# Permutations CSES Solution

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

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

Input

The only input line contains an integer n.

Output

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

Constraints

• 1≤n≤1061≤n≤106

Example 1

Input:
`5`

Output:
`4 2 5 3 1`

Example 2

Input:
`3`

Output:
`NO SOLUTION`

Code Solution

```//Permutations CSES Solution

import java.util.*;
import java.lang.*;
import java.io.*;

public class BeautiNumber{

public static void main(String args[]) throws IOException
{

if(n==1){
System.out.println(1);
}

else if(n==2 || n==3){
System.out.println("NO SOLUTION");
}
else{
StringBuilder out=new StringBuilder();
for(int i=2; i<=n; i+=2)out.append(i+" ");
for(int i=1; i<=n; i+=2)out.append(i+" ");
System.out.print(out);

}
}
}

//Permutations CSES Solution```