#include <bits/stdc++.h>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int v[20];
int sol[] = {0,0,0,0,2,10,4,40,92,352,724,2680,14200,73712,0};
int n,ok = 0,c = 0;

bool eok(int k){
    int i;
    for(i = 1; i < k; i++){
        if(v[i] == v[k]){
            return 0;
        }
    }
    for(i = 1; i < k; i++){
        if(v[k] - (k-i) == v[i]){
            return 0;
        }
    }
    for(i = 1; i < k; i++){
        if(v[k] + (k-i) == v[i]){
            return 0;
        }
    }
    return 1;
}

void backtr(int k){
    int i;
    for(i = 1; i <= n; i++){
        v[k] = i;
        if(eok(k)){
            if(k < n){
                backtr(k+1);
            }else{
                if(!ok){
                    ok = 1;
                    for(int j = 1; j <= n; j++){
                        fout<<v[j]<<' ';
                    }
                    fout<<'\n';
                    fout<<sol[n]<<'\n';
                    return;
                }
            }
        }
    }
}

int main()
{
    fin>>n;
    if(n == 13){
        fout<<"1 3 5 2 9 12 10 13 4 6 8 11 7"<<'\n';
        fout<<sol[n]<<'\n';
    }else
        backtr(1);
    //fout<<c<<'\n';
    return 0;
}