using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace nqueens
{
	class Program
	{
		static void Main(string[] args)
		{
			var n = Convert.ToInt32(args[0]);
			var lsQueens = new MinConflictsQueens(n);
			var solution = lsQueens.Solve();

			if (solution != null)
			{
				var s = string.Join(" ", solution.Select(i => i.ToString()));
				Console.WriteLine(n);
				Console.WriteLine(s);
				Debug.WriteLine(n);
				Debug.WriteLine(s);
			}
			else
			{
				Console.WriteLine("No solution");
			}
		}
	}

	public class MinConflictsQueens
	{
		private readonly int _n;

		public MinConflictsQueens(int n)
		{
			_n = n;
		}

		private NBoard Initial()
		{
			//var random = new Random(1);
			//var randValues = (from i in Enumerable.Range(0, _n)
			//			 select random.Next(0, _n)).ToArray();

			//var board = new List<int>(_n);
			//for (var i = 0; i < _n; i++)
			//{
			//	if (i % 2 == 0)
			//		board.Insert(0,i);
			//	else
			//		board.Insert(i,i);

			//}

			//return new NBoard(board.ToArray());

			var board = new int[_n];
			var n2 = _n/2;
			for (var i = 1; i <= n2; i++)
			{
				board[i - 1] = 2*i - 1;
				board[n2 + i - 1] = 2* (i - 1);
			}
			//board[n2 - 1] = 0;
			return new NBoard(board);
		}

		public IList<int> Solve()
		{
			var nBoard = Initial();
			var random = new Random();
			int lastColumn = -1;
			int iterations = 0;

			while (true)
			{
				if (nBoard.IsFeasible())
					return nBoard.Columns;

				if (++iterations % 100 == 0)
					Debug.WriteLine("{0} : {1}", iterations, nBoard.Conflicts.Sum());

				// select the next biggest conflict count
				var maxConflictColumn = 
					(from c in Enumerable.Range(0, _n)
					 let conflicts = nBoard.Conflicts[c]
					 select new {c, conflicts})
						.GroupBy(arg => arg.conflicts)
						.OrderByDescending(grouping => grouping.Key)
						.First()
						.OrderBy(arg => random.Next())
						.First()
						.c;

				if (maxConflictColumn == lastColumn)
					maxConflictColumn = random.Next(0, _n);
				lastColumn = maxConflictColumn;

				var minConflictRow =
					(from row in Enumerable.Range(0, _n)
					 let conflicts = nBoard.TestConflictCount(maxConflictColumn, row)
					 select new {row, conflicts})
						.GroupBy(arg => arg.conflicts)
						.OrderBy(grouping => grouping.Key)
						.First()
						.OrderBy(arg => random.Next())
						.First()
						.row;

				nBoard.UpdateRow(maxConflictColumn, minConflictRow);
			}
		}
	}
}