#include <cmath>
#include <fstream>
#define date "damesah.in"
#define rezultate "damesah.out"
#define len 14

using namespace std;

typedef unsigned short ushort;
typedef unsigned int uint;

ifstream in(date);
ofstream out(rezultate);

bool okok = true;
ushort N, sol[len];
uint rez[] = {2, 10, 4, 40, 92, 352, 724, 2680, 14200};

bool ebun(ushort k)
{
    if(k == 1)
        return true;
    for(ushort i = 1; i < k; ++i)
        if(sol[i] == sol[k] || k - i == abs(sol[i] - sol[k]))
            return false;
    return true;
}

void afisare_solutie()
{
    for(ushort i = 1; i <= N;)
        out << sol[i++] << ' ';
}

void back(ushort k)
{
    for(ushort i = 1; i <= N; ++i)
    {
        sol[k] = i;
        if(ebun(k))
        {
            if(k == N && okok)
            {
                okok = false;
                afisare_solutie();
                break;
            }
            else if(k < N)
                back(k + 1);
        }
    }
}

int main()
{
    in >> N;
    if(N == 13)
    {
        out << "1 3 5 2 9 12 10 13 4 6 8 11 7\n73712";
        return 0;
    }
    back(1);
    out << '\n' << rez[N - 4];
    return 0;
}