Question: A permutation of integers 1,2,…,$n$ is called beautiful if there are no adjacent elements whose difference is 1. 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,…,$n$. If there are several solutions, you may print any of them. If there are no solutions, print “NO SOLUTION”.

Input:
5

Output:
4 2 5 3 1

Input:
3

Output: 

NO SOLUTION

#include<bits/stdc++.h>

using namespace std;

int main()
{
  long long n;cin>>n;
  if (n == 1)
  {
    cout << n << "/n";
    exit(0);
  }
  if (n <= 3)
      cout << "NO SOLUTION" << endl;
  else
  {
    int start = n & 1 ? n - 1:n;
    for (int i = start - 1; i > 0; i = i - 2)
      cout << i << " ";
    for (int i = start; i >= 2; i = i - 2)
      cout << i << " ";
    if (n & 1)
      cout << n;
    cout << "\n";
  }
  return 0;
}