lzs

// I'm the bone of my code. Syntax is my body, Data is my blood ...
#include<bits/stdc++.h>
#define FILE "lzs"
using namespace std;

const int mod = 1e9 + 9;
const int N = 2e4 + 10;
const int inf = 1e9 + 10;

int n, m;
int a[N], b[N];

int vis[N];
int dp[N][2], num[N][2];

void add(int &a, int &b, int c, int d)
{
    if (a < c) a = c, b = d;
    else
    if (a == c) b = ((b + d) % mod + mod) % mod;
}

void solve()
{
    for (int i = 1; i <= n; i++)
        dp[i][0] = 0, dp[i][1] = -inf;
    // 0 la chan, 1 la le
    for (int i = 1; i <= n; i++)
    {
        // i is da best
        int best[2] = {0, -inf};
        int acc[2] = {1, 0};

        for (int j = 1; j <= m; j++)
        {
            if (a[i] == b[j]) // always reset
            {
                for (int type = 0; type < 2; type++)
                    dp[j][type] = 0, num[j][type] = 0,
                    add(dp[j][type], num[j][type], best[1 - type] + 1, acc[1 - type]);
                continue;
            }

            int curType = (a[i] > b[j] ? 1 : 0);
            if (vis[ b[j] ])
            {
                int old = vis[ b[j] ];
                assert(b[old] == b[j]);
                add(best[curType], acc[curType], dp[old][curType], -num[old][curType]);
            }
            vis[ b[j] ] = j;
            add(best[curType], acc[curType], dp[j][curType], num[j][curType]);

        }
        for (int j = 1; j <= m; j++) vis[ b[j] ] = 0;
    }

    int resx = 0, resy = 0;
    for (int i = m; i >= 1; i--)
        if (!vis[b[i]])
        {
            add(resx, resy, dp[i][1], num[i][1]),
            vis[b[i]] = 1;
        }

    cout << resx << ' ' << resy << '\n';
}

int main()
{
    if (fopen("main.in", "r"))
        assert(freopen("main.in", "r", stdin));
    else
    if (fopen(FILE".in", "r"))
        assert(freopen(FILE".in", "r", stdin)),
        assert(freopen(FILE".out", "w", stdout));

    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> b[i];

    solve();
}