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
{   
        BufferedReader x=new BufferedReader(new InputStreamReader(System.in));
		long n=Integer.parseInt(x.readLine());
 
 
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