Олімпійська система

Двоє керівників організовують змагання серед $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$ визначте максимальну кількість послідовностей, які можна отримати вищеописаним чином, серед яких немає жодної пари еквівалентних.