//N皇后構造解,n>=4

void even1(int n,int *p){
	int i;
	for (i=1;i<=n/2;i++) 
		p[i-1]=2*i;
	for (i=n/2+1;i<=n;i++) 
		p[i-1]=2*i-n-1;
}

void even2(int n,int *p){
	int i;
	for (i=1;i<=n/2;i++)
		p[i-1]=(2*i+n/2-3)%n+1;
	for (i=n/2+1;i<=n;i++)
		p[i-1]=n-(2*(n-i+1)+n/2-3)%n;
}

void generate(int,int*);
void odd(int n,int *p){
	generate(n-1,p),p[n-1]=n;
}

void generate(int n,int *p){
	if (n&1)
		odd(n,p);
	else if (n%6!=2)
		even1(n,p);
	else
		even2(n,p);
}