#include<cstdio>
using namespace std;
int sol[20],N,Nr_Sol=0;
bool pus[20];
inline int modul(int x)
{
    if (x<0) return -x;
        else return x;
}
inline void Write()
{
    for (int i=1;i<=N;++i)
        printf("%d ",sol[i]);
}
inline void Back(int k)
{
    if (k>N) {
                Nr_Sol++;
                if (Nr_Sol==1) Write();
             }
        else for (int i=1;i<=N;++i)
                if (!pus[i] && modul(sol[k-1]-i)>1)
                    {
                        pus[i]=true;
                        sol[k]=i;
                        Back(k+1);
                        pus[i]=false;
                    }
}
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&N);
    sol[0]=200000;
    Back(1);
    printf("\n%d\n",Nr_Sol);
    fclose(stdin); fclose(stdout);
    return 0;
}