Гондола

Гондола Мао-Конга — популярна пам'ятка Тайбея. Це канатна дорога у формі кола з однією станцією та 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 ≤ i ≤ n - 1;

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

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

Приклади

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

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

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

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

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

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

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

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

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

Приклади

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

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

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

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

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

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

Приклади

Вхідні дані

Перша рядок містить номер підзадачі t, яку повинна вирішувати ваша програма (1 ≤ t ≤ 10);

Друга рядок містить довжину n переданої послідовності;

Якщо t дорівнює 4, 5 або 6, то третя рядок містить gondolaSeq[0], ..., gondolaSeq[n-1]. Інакше вона містить inputSeq[0], ..., inputSeq[n-1].

Вихідні дані

Для кожного питання буде виведено відповідну відповідь.

Приклади