Генетичні алгоритми

Генетичні алгоритми — один з сучасних методів штучного інтелекту. Вони базуються на принципі природного відбору, який був запропонований Чарльзом Дарвіном, і є одним з різновидів еволюційних обчислень.

У процесі роботи генетичного алгоритму підтримується деяка множина допустимих розв'язків задачі, яка називається поколінням. Робота алгоритму полягає в генерації чергового покоління. Для цього використовуються так звані операції "мутації" та "зхрещування". Як правило, операція мутації складається у невеликій зміні розв'язкау, а операція зхрещування — у побудові з двох розв'язків одного чи двох нових.

Одним із застосувань генетичних алгоритмів є розв'язання задачі комівояжера. Допустимими розв'язками у цій задачі є перестановки чисел від 1 до n — такі послідовності довжинм n, у яких кожне з цих чисел зустрічається рівно один раз.

Деякі генетичні а0лгоритми, які розв'язують задачу комівояжера, використовують операції зхрещування, які генерують лише так звані узгоджені перестановки. Нехай задано дві перестановки. Назвемо третю перестановку узгодженою з першими двома, якщо для довільної пари чисел (i, j) такої, що в обох перестановках число i йде раніше, ніж число j, і у новій перестановці i йде раніше j.

Для аналізу таких алгоритмів корисно вміти визначати кількість перестановок, узгоджених з заданими двома. Ваша задача полягає у тому, щоб написати програму, яка буде обчислювати цю кількість.

Вхідні дані

Перший рядок вхідного файлу містить число n (1 ≤ n ≤ 20). Другий рядок вхідного файлу містить n чисел — першу перестановку, а третій рядок містить другу перестановку.

Вихідні дані

У вихідний файл виведіть відповідь до задачі.