Олимпийская система

   Двое руководителей организуют соревнования среди N команд по олимпийской системе. Все команды перенумерованы числами от 1 до N. Наши руководители очень занятые люди. Поэтому они определяют только кому проводить очередной матч, выбирая каждый раз команды с соседними номерами. Все остальное делают их ассистенты. После завершения матча проигравший выбывает, а еще не выбывшие команды, имеющие более высокие номера (если таковые есть), сдвигаются на 1 номер вперед (т.е. уменьшают свои номера на 1) и руководитель (тот, который в этот момент более свободен) приглашается для выбора очередной пары команд (одновременно оба руководителя свободными быть не могут). Соревнования заканчиваются, когда остается только одна команда. Решениям руководителей можем поставить в соответствие последовательность чисел, полученную выписыванием меньших номеров команд для каждой пары, выбранной руководителем.

   Например, если команд было 4, а соперничающие пары выбирались в следующем порядке: (1, 2), (2, 3), (1, 2), то получаем последовательность 1, 2, 1. Заметим, что некоторые последовательности определяют одинаковые пары соперничающих команд, отличающиеся только порядком проведения матчей. Такие последовательности будем называть эквивалентнными.

   Например, приведенная выше последовательность эквивалентна последовательности 3, 1, 1. Действительно, в терминах исходных номеров, в первом случае, вначале встречаются команды 1, 2, затем 3, 4, а затем победители этих пар встречаются между собой. Во втором случае, наоборот, вначале встречаются 3, 4, затем 1, 2, после чего победители пар встречаются друг с другом.

   Для заданного N определить максимальное количество последовательнстей, которые можно получить вышеописанным образом, среди которых нет ни одной пары эквивалентных.

1 

1