皇后控制问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在一个n× n个方格组成的棋盘上的任一方格中放置一个皇后,该皇后可以控制他所在的行,列以及对角线上的所有方格。对于给定的自然数n,在n× n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格,且放置的皇后互不攻击?
设计一个拉斯维加斯算法,对于给定的自然数n (1≤ n ≤100)计算在n× n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格,且放置的皇后互不攻击。

Input

输入数据只占一行,有1 个正整数n。

Output

将计算出最少皇后数及最佳放置方案输出。第一行是最少皇后数;接下来的1 行是皇后的最佳放置方案。

Sample Input

8

Sample Output

5
0 3 6 0 0 2 5 8

Hint

Source