19086번 - Leave Out All The Rest 다국어

You are given two integer arrays: an array $a$ of length $n$ and an array $b$ of length $m$. All integers in both arrays are pairwise distinct.

An interleaving of the two arrays is an array $c$ of size $n + m$ such that arrays $a$ and $b$ are its disjoint subsequences. Formally, there exist indices $i_1 < i_2 < \ldots < i_n$ such that $c_{i_1} = a_1$, $c_{i_2} = a_2$, $\ldots$, $c_{i_n} = a_n$, and indices $j_1 < j_2 < \ldots < j_m$ such that $c_{j_1} = b_1$, $c_{j_2} = b_2$, $\ldots$, $c_{j_m} = b_m$. For these indices, $i_x \neq j_y$ for all $x = 1, 2, \ldots, n$ and all $y = 1, 2, \ldots, m$.

It is clear that there are usually many ways to interleave arrays $a$ and $b$. Find such a way that maximizes the length of the longest increasing subsequence of $c$.

The first line of input contains integer $n$ ($1 \le n \le 5 \cdot 10^5$) --- the length of array $a$.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$).

The third line of input contains integer $m$ ($1 \le m \le 5 \cdot 10^5$) --- the length of array $b$.

The fourth line contains $m$ integers $b_j$ ($1 \le b_j \le 10^9$).

It is guaranteed that the numbers in both arrays are pairwise distinct: $a_i \neq a_j$ for $i \neq j$, $b_i \neq b_j$ for $i \neq j$ and $a_i \neq b_j$ for all valid $i$ and $j$.

Output one integer: the maximum length of the longest increasing subsequence in an interleaving of $a$ and $b$.