Сложная задача

면접 대비

시간 제한2초메모리 제한1024 MB

요약

두 이진 수열이 주어질 때, 각각의 부분수열이면서 감소하지 않는 가장 긴 공통 부분수열의 길이를 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 그리디, 배열, 누적 합
정답자: 아직 제출이 없습니다

문제

Чтобы выбраться из игры, доктору Смолдеру Брэйвстоуну надо решить сложную задачу. Ему надо для двух последовательностей, состоящих из нулей и единиц, найти максимальную длину последовательности, которая является подпоследовательностью каждой из них, и при этом неубывает.

Поскольку доктор Смолдер Брэйвстоун гораздо более хорош в бросании бумерангов, чем в решении подобных задач, он попросил вас помочь ему. Вам требуется найти длину наибольшей общей неубывающей подпоследовательности двух последовательностей из нулей и единиц.

입력

Первая строка входных данных содержит единственное целое число $n$ --- длину первой последовательности ( $1 \le n \le 2 \cdot 10^5$ ).

Вторая строка содержит $n$ целых чисел $a\_i$ --- элементы первой последовательности ( $0 \le a\_i \le 1$ ).

Третья строка содержит единственное целое число $m$ --- длину второй последовательности ( $1 \le m \le 2 \cdot 10^5$ ).

Четвертая строка содержит $m$ целых чисел $b\_i$ --- элементы второй последовательности ( $0 \le b\_i \le 1$ ).

출력

Выведите единственное целое число — длину наибольшей общей неубывающей подпоследовательности данных последовательностей.

힌트

В тесте из условия наибольшей общей неубывающей подпоследовательностью данных последовательностей является последовательность $\\{0, 0, 1, 1, 1\\}$ . Она имеет длину $5$ .

예제1

예제 1
입력
```
7
0 0 0 1 0 1 1
6
0 0 1 1 0 1
```
예상 출력
```
5
```