Республиканская олимпиада по информатике 2017 год, Павлодар

Задача D. Красивая последовательность

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

16 мегабайт

Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов. Вам даны две последовательности целых неотрицательных чисел размера $n$: $a_1, a_2, \ldots, a_n$ и размера $m$: $b_1, b_2, \ldots, b_m$. Назовем последовательность из $k$ целых чисел $c_1, c_2, \ldots, c_k$ красивой, если выполняются следующие условия:

• k является нечетным.
• $c_{2*j-1} < c_{2 * j}$ и $c_{2*j+1} < c_{2 * j}$ для всех $1 < 2 * j < k$.
• Последовательность $c_1, c_2, \ldots, c_k$ является подпоследовательностью последовательности $a_1, a_2, \ldots, a_n$.
• Последовательность $c_1, c_2, \ldots, c_k$ является подпоследовательностью последовательности $b_1, b_2, \ldots, b_m$.

Найдите максимальную длину красивой последовательности и количество различных красивых последовательностей максимальной длины по модулю $10^9 + 9$.

Формат входного файла

В первой строке входных данных дано целое положительное число $n$ ($1 \le n \le 10^4$)~— размер последовательности $a$. Вторая строка содержит $n$ целых неотрицательных чисел $a_i$ ($1 \le a_i \le 20000$)~— последовательность $a$. В третьей строке содержится целое положительное число $m$ ($1 \le m \le 10^4$)~— размер последовательности $b$.Четвертая строка содержит $m$ целых неотрицательных чисел $b_i$ ($1 \le b_i \le 20000$)~— последовательность $b$. Числа в обеих последовательностях задаются через одиночный пробел.

Формат выходного файла

Выведите два целых числа ответ на задачу. Если ответа несуществует выведите два нуля.

Система оценки

Данная задача содержит четыре подзадачи:

1. $1 \leq n \leq 20$, $1 \le m \le 10$. Оценивается в $9$ баллов.
2. $1 \leq n \leq 1000$, $1 \le m \le 20$. Оценивается в $9$ баллов.
3. $1 \leq n \leq 500$, $1 \le m \le 500$. Оценивается в $28$ баллов.
4. $1 \leq n \leq 10^4$, $1 \le m \le 10^4$. Оценивается в $54$ баллов.

Примеры:

Вход

1
1
1
2

Ответ

0 0

Вход

7
1 5 3 4 2 5 2
5
1 3 5 4 2

Ответ

3 6

Вход

4
1 1 3 2
4
1 3 2 2

Ответ

3 1

( Aidos Nurmash )