(1) + Насчет начальной позиции. Я провел маленькое исследование решаемости/нерешаемости. Т.е. есть и другой вариант подсказки - анализ количества инверсий справа и слева + алгоритм одновременногй смены четности количества инверсий справа и слева. Но это очень длинно получилось...