E. LIS Maximization
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$.

You are creating a new array $$$c$$$. Initially, it is empty. On step $$$i$$$, you add either $$$a_i$$$ or $$$b_i$$$ to the end of the array.

Your task is to construct array $$$c$$$ in such a way that the length of the Longest Increasing Subsequence of $$$c$$$ is maximized.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the arrays.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)  — elements of array $$$a$$$.

The third line contains $$$n$$$ integers $$$b_1, \dots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — elements of array $$$b$$$.

Output

Output the length of the Longest Increasing Subsequence in the constructed array $$$c$$$.

Examples
Input
6
1 4 3 5 2 9
4 3 1 2 5 1
Output
4
Input
5
1 9 4 5 6
1 9 10 5 6
Output
4
Note

In the first sample, you can choose $$$c = \{a_1, b_2, a_3, a_4, b_5, a_6\}$$$.

The values of $$$c$$$ are $$$\{\color{orange}1, 3, \color{orange}3, \color{orange}5, 5, \color{orange}9\}$$$. The elements highlighted in orange form the Longest Increasing Subsequence of length $$$4$$$.