Problem Description

Farmer John has $N$ cows ($1 \le N \le 20$) with heights $a_1 \ldots a_N$. His barn has $N$ stalls, with height limits $b_1 \ldots b_N$ (for example, if $b_5 = 17$, then a cow of height at most $17$ can live in stall $5$). How many different ways can Farmer John assign his cows so that each cow lives in a different stall and every stall’s height limit is satisfied?

Input Format

The first line contains $N$. The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$. The third line contains $N$ space-separated integers $b_1, b_2, \ldots, b_N$. All heights and height limits are in the range $[1, 10^9]$.

Output Format

Output the number of ways Farmer John can assign each cow to a different stall such that every stall’s height limit is satisfied. Note that the answer may require a 64-bit integer type, such as long long in C++.

4
1 2 3 4
2 4 3 4

8

Hint

Sample Explanation 1

In this example, we cannot assign the third cow to the first stall because $3 = a_3 > b_1 = 2$. Similarly, we cannot assign the fourth cow to the first or third stall. One valid assignment that satisfies the height limits is to put cow 1 in stall 1, cow 2 in stall 2, cow 3 in stall 3, and cow 4 in stall 4.

Test Point Properties

• Test points $1-5$ satisfy $N \le 8$.
• Test points $6-12$ have no additional constraints.

Translated by ChatGPT 5