Гондола

Гондола Мао-Конга — популярна пам'ятка Тайбея. Це канатна дорога у формі кола з однією станцією та $n$ гондолами, пронумерованими від $1$ до $n$. Гондоли рухаються в одному напрямку. Спочатку, після гондоли з номером $i$ повз станцію проїжджає гондола з номером ($i$ + $1$) для $i$ < $n$. Якщо $i$ = $n$, то наступною проїжджає гондола з номером $1$.

Іноді гондоли можуть виходити з ладу. На щастя, у нас є необмежена кількість запасних гондол, які мають номери ($n$ + $1$), ($n$ + $2$) і так далі. Коли гондола ламається, її замінюють запасною з найменшим номером серед тих, які ще не були використані. Нова гондола встановлюється на те ж місце, де стояла зламана. Наприклад, якщо було п'ять гондол, і одна з них зламалася, то її замінять на гондолу з номером $6$.

Вам подобається стояти на станції і спостерігати за гондолами, що проїжджають повз. Послідовністю гондол називається послідовність з $n$ номерів гондол у порядку, в якому вони проїжджають повз станцію. Можливо, що одна або кілька гондол зламалися до того, як ви прийшли на станцію, але поки ви дивитеся на рух гондол, жодна з них не ламається.

Зверніть увагу, що одному й тому ж порядку гондол може відповідати кілька послідовностей, залежно від того, яка з гондол приїхала на станцію першою. Наприклад, якщо жодна з гондол не ламалася, то можливі послідовності гондол ($2$, $3$, $4$, $5$, $1$) і ($4$, $5$, $1$, $2$, $3$), а ($4$, $3$, $2$, $5$, $1$) — не є послідовністю гондол, тому що гондоли приїхали в неправильному порядку.

Якщо гондола з номером $1$ зламається, то ви зможете побачити послідовність гондол ($4$, $5$, $6$, $2$, $3$). Якщо після цього зламається гондола з номером $4$, її замінять на гондолу з номером $7$, і ви зможете побачити послідовність ($6$, $2$, $3$, $7$, $5$). Якщо після цього гондола з номером $7$ зламається, її замінять на гондолу з номером $8$, і ви зможете побачити послідовність ($3$, $8$, $5$, $6$, $2$).

Послідовністю замін називається послідовність номерів зламаних гондол у тому порядку, в якому вони ламалися. У попередньому прикладі послідовність замін — ($1$, $4$, $7$). Вважатимемо, що послідовність замін $r$ породжує послідовність гондол $g$, якщо після того, як гондоли ламалися і замінювалися відповідно до послідовності замін $r$, ви можете побачити послідовність гондол $g$.

Перевірка послідовності гондол

У перших трьох підзадачах вам необхідно перевірити, чи є послідовність гондол коректною. Вам потрібно реалізувати функцію valid($n$, inputSeq), де

• $n$ — довжина послідовності;

• inputSeq — масив довжини $n$, inputSeq[i] — елемент послідовності на місці $i$ для 0 \leq i \leq n - 1;

• функція повинна повертати $1$, якщо передана послідовність є послідовністю гондол, і $0$ в іншому випадку.

Підзадачі 1, 2, 3

Приклади

У таблиці нижче наведені приклади послідовностей, які є і не є послідовностями гондол.

Послідовність замін

У наступних трьох підзадачах ви повинні побудувати послідовність замін, яка породжує задану послідовність гондол. Ви можете побудувати будь-яку з таких послідовностей.

Вам потрібно реалізувати функцію replacement($n$, gondolaSeq, replacementSeq), де

• $n$ — довжина послідовності;

• gondolaSeq — масив довжини $n$. Гарантовано, що gondolaSeq є послідовністю гондол, gondolaSeq[i] — це $i$-ий елемент послідовності, для 0 \leq i \leq n - 1;

• функція повинна повертати $l$ — довжину послідовності замін;

• replacementSeq — масив, достатньо великий, щоб вмістити послідовність замін; ви повинні повернути послідовність замін, записавши її $i$-ий елемент у replacementSeq[i] для всіх 0 \leq i \leq l - 1.

Підзадача 4, 5, 6

Приклади

Підрахунок послідовностей замін

У наступних чотирьох підзадачах ви повинні визначити кількість послідовностей замін, які породжують задану послідовність (яка може бути послідовністю гондол, а може не бути) за модулем 10^9 + $9$. Ви повинні реалізувати функцію countReplacement($n$, inputSeq).

• $n$ — довжина переданої послідовності;

• inputSeq — масив довжини $n$, inputSeq[i] — це $i$-ий елемент переданої послідовності, для всіх 0 \leq i \leq n - 1.

• якщо передана послідовність є послідовністю гондол, ви повинні визначити кількість послідовностей замін, які породжують дану послідовність гондол, і повернути залишок від ділення цієїкількості на 10^9 + $9$. Якщо передана послідовність не є послідовністю гондол, функція повинна повертати $0$. Якщо передана послідовність є послідовністю гондол, але жодна гондола не зламалася, функція повинна повернути $1$.

Підзадачі 7, 8, 9, 10

Приклади