Maximum Non-Intersecting Bridges

You are given two lists of n integers representing the positions of potential bridge connection points on each bank of a river. The first list, A, gives the positions on the left bank and the second list, B, gives the positions on the right bank. Each pair (A[i], B[i]) represents a proposed bridge.

Your task is to determine the maximum number of bridges that can be built such that no two bridges intersect. Two bridges (A[i], B[i]) and (A[j], B[j]) intersect if and only if they cross each other. A standard approach to solving this problem involves:

• Sorting the bridges by their A values.
• Finding the length of the longest increasing subsequence (LIS) of the B values afterwards. In mathematical terms, if we denote the sorted B sequence as B', you are to maximize the number of indices such that $$B'_{i_1} < B'_{i_2} < \cdots < B'_{i_k}.$$

This problem may be solved efficiently using binary search in combination with a dynamic programming approach to compute the LIS.

inputFormat

The input is read from standard input (stdin) and consists of three lines:

1. The first line contains a single integer n denoting the number of bridge proposals.
2. The second line contains n space-separated integers representing the positions on the left bank (list A).
3. The third line contains n space-separated integers representing the positions on the right bank (list B).

outputFormat

Output a single integer to standard output (stdout) which represents the maximum number of bridges that can be built without any two bridges intersecting.## sample

5
1 3 5 2 4
2 4 1 5 3

2