Dãy con chung

Cho dãy \(A\) gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Giá trị \(n\) được gọi là độ dài của dãy \(A\).

Dãy con của \(A\) là chính \(A\) hoặc là dãy nhận được từ dãy ban đầu bằng cách bỏ đi một số phần tử.

Dãy \(A\) được gọi là dãy không giảm nếu thỏa mãn:

Ví dụ dãy: \(2, 2, 4, 9, 3, 10\) ta có một số dãy con như sau: \(2, 2, 4, 10\); \(2, 9, 3\); \(2, 9, 10\). Trong đó, các dãy con \(2, 2, 4, 10\) và \(2, 9, 10\) được gọi là các dãy con không giảm.

Cho dãy \(A\) gồm \(n\) số nguyên, dãy \(B\) gồm \(m\) số nguyên. Dãy \(C\) được gọi là dãy con chung của hai dãy \(A\) và \(B\) nếu \(C\) vừa là dãy con của \(A\), vừa là dãy con của \(B\).

Ví dụ: Cho dãy \(A = (1, 2, 4, 9, 3)\) và dãy \(B = (0, 2, 15, 9)\). Dãy \(C = (2, 9)\) là một dãy con chung của hai dãy \(A\) và \(B\).

Yêu cầu. Cho hai dãy \(A\) và \(B\) chỉ chứa các số \(0\) và \(1\), dãy \(A\) có \(n\) phần tử, dãy \(B\) có \(m\) phần tử. Hãy xác định độ dài lớn nhất của dãy con chung không giảm của \(A\) và \(B\).

Input

• Dòng đầu chứa một số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)) là số phần tử của dãy \(A\);
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 1\), \(i = 1, 2, \dots, n\)) là các phần tử của dãy \(A\);
• Dòng thứ ba chứa một số nguyên \(m\) (\(1 \le m \le 2 \cdot 10^5\)) là số phần tử của dãy \(B\);
• Dòng thứ tư chứa \(m\) số nguyên \(b_1, b_2, \dots, b_m\) (\(0 \le b_i \le 1\), \(i = 1, 2, \dots, m\)) là các phần tử của dãy \(B\).

Dữ liệu của bài toán đảm bảo luôn tồn tại dãy con chung.

Output

• Ghi một số nguyên duy nhất là độ dài lớn nhất của dãy con chung không giảm của hai dãy \(A\) và \(B\).

Input

%
7
0 0 0 1 0 1 1
6
0 0 1 1 0 1

Output

%
5

Input

%
10
0 0 0 1 1 1 0 1 0 0
10
1 1 0 0 0 1 0 1 1 1

Output

%
7

Input

%
3
1 1 1
5
1 0 1 0 0

Output

%
2

Notes

Trong ví dụ thứ nhất, dãy con chung không giảm dài nhất là: \(0, 0, 1, 1, 1\).

Scoring

• (25%) \(a_i = 1\) với mọi \(i = 1, 2, \dots, n\); \(1 \le m, n \le 3000\);
• (25%) \(m = n\), \(a_i = b_i\) với mọi \(i = 1, 2, \dots, n\);
• (25%) \(1 \le m, n \le 3000\);
• (25%) Không có ràng buộc thêm.