Having crossed the river, Coderun plunged into the binary forest and has already found a path that needs to be followed to catch the enemy. You just can't escape him! He immediately noticed a parallel path.
Unfortunately, carbon-based life forms cannot interfere in the binary world. But we can help Coderun!
Both paths are represented by binary sequences of lengths
To continue the chase, you need to understand how far they can go "on foot". For this, you need to find the maximum length of a non-decreasing common subsequence that can be obtained by crossing out some elements from both sequences.
The function takes 4 parameters as arguments:
- An integer
$n$ ($1 \le n \le 2 \cdot 10^5$ ) — the number of elements in the first sequence. - A one-dimensional array of integers
$a$ of size$n$ ($0 \le a_i \le 1$ ) — elements of the first sequence. - An integer
$m$ ($1 \le m \le 2 \cdot 10^5$ ) — the number of elements in the second sequence. - A one-dimensional array of integers
$b$ of size$m$ ($0 \le b_i \le 1$ ) — elements of the second sequence.
As an answer, your program should return a single integer — the length of the longest common non-decreasing subsequence of the given sequences.
A subsequence
$1 \le i_1 < i_2 < \dots < i_p \le k$ -
$p$ — the length of the subsequence.
A common subsequence
In the test case, the longest common non-decreasing subsequence of the given sequences is
- It has length 5.
- In sequence
$A$ , it is located at positions$[1, 2, 4, 6, 7]$ . - In sequence
$B$ , it is located at positions$[1, 2, 3, 4, 6]$ .
- Time limit: 2 seconds
- Memory limit: 256 MB
Input
7
0 0 0 1 0 1 1
6
0 0 1 1 0 1
Output
5