Genetic Algorithms
Genetic algorithms are a modern approach in artificial intelligence, inspired by Charles Darwin's principle of natural selection, and are a form of evolutionary computation.
In a genetic algorithm, a set of potential solutions, known as a generation, is maintained. The algorithm's task is to produce the next generation using operations called "mutation" and "crossover." Typically, a mutation involves a minor alteration to a solution, while a crossover creates one or two new solutions from two existing ones.
One application of genetic algorithms is solving the traveling salesman problem. In this problem, feasible solutions are permutations of numbers from 1 to n—sequences of length n where each number appears exactly once.
Some genetic algorithms for the traveling salesman problem use crossover operations that generate only what are called consistent permutations. Given two permutations, a third permutation is considered consistent with the first two if, for any pair of numbers (i, j), where i precedes j in both permutations, i also precedes j in the new permutation.
For analyzing such algorithms, it is useful to determine the number of permutations consistent with the given two. Your task is to write a program that calculates this number.
Input
The first line of the input contains the number n (1 ≤ n ≤ 20). The second line contains n numbers representing the first permutation, and the third line contains the second permutation.
Output
Output the solution to the problem.