A Hard Problem

Interview

Time limit2sMemory limit1024 MB

Summary

Given two binary sequences, find the length of the longest common subsequence that is non-decreasing.

Level: Medium5 of 10
Topics: String, Prefix sum, Dynamic programming
Solved: No attempts yet

Statement

To escape from the game, Doctor Smolder Braveston has to solve a hard problem. You are given two sequences consisting of zeros and ones. Find the maximum length of a sequence that is a subsequence of both and is non-decreasing. The doctor is much better at throwing boomerangs than at solving problems like this, so he asked you for help.

Input

The first line contains a single integer $n$ , the length of the first sequence ( $1 \le n \le 2 \cdot 10^5$ ). The second line contains $n$ integers $a_i$ , the elements of the first sequence ( $0 \le a_i \le 1$ ). The third line contains a single integer $m$ , the length of the second sequence ( $1 \le m \le 2 \cdot 10^5$ ). The fourth line contains $m$ integers $b_i$ , the elements of the second sequence ( $0 \le b_i \le 1$ ).

Output

Print a single integer, the length of the longest common non-decreasing subsequence of the two sequences.

Hint

In the example from the statement, the longest common non-decreasing subsequence is {0, 0, 1, 1, 1}, which has length 5.

Examples1

Example 1
Input
```
7
0 0 0 1 0 1 1
6
0 0 1 1 0 1
```
Expected output
```
5
```