/*

最长公共上升子序列 https://www.acwing.com/problem/content/274/

第一二个序列分别为a b

状态表示 
集合 - f[i,j]所有由第一个序列前i个字母，第二个序列前j个字母构成的（公共）
      且以b[j]结尾的公共上升子序列（上升）
属性 - Max

状态计算
所有包含a[i]的公共上升子序列
    - a[i] = b[j]
    - 根据倒数第二个字母，划分为
        空 / b[1] / b[2] / ... b[j-1]
        对于第k类，先抛开b[j]
            表示所有以第一个序列前i个字母，第二个序列前k个字母构成且以b[k]结尾的公共上升子序列
            加上b[j]表示为 f[i,k] + 1
所有不包含a[i]的公共上升子序列 f[i-1][j]
    - 即以第一个序列前i-1个字母和第二个序列前j个字母构成的，以b[j]结尾的公共上升子序列




*/

//o(n^3)

#include <iostream>
using namespace std;

const int N = 3010;
int a[N], b[N], f[N][N];
int res, n;

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

    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= n; j ++ ) 
        {
            f[i][j] = f[i - 1][j];
            if ( a[i] == b[j] ) 
            {
                f[i][j] = max(f[i][j], 1);
                for ( int k = 1; k < j; k ++ )
                    if ( b[j] > b[k] ) 
                        f[i][j] = max(f[i][j], f[i][k] + 1);
            }
        }
    for ( int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    cout << res;
    return 0;
}

//优化

#include <iostream>
using namespace std;

const int N = 3010;
int a[N], b[N], f[N][N];
int res, n;

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

    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= n; j ++ ) 
        {
            f[i][j] = f[i - 1][j];
            if ( a[i] == b[j] ) 
            {
                f[i][j] = max(f[i][j], 1);
                for ( int k = 1; k < j; k ++ )
                    if ( a[i] > b[k] )  //a[i] == b[j] 将b[j]换成a[i]，这时该条件与j没有关系，可以提到循环外面  
                        f[i][j] = max(f[i][j], f[i][k] + 1);
            }
        }
    for ( int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    cout << res;
    return 0;
}

// -->

#include <iostream>
using namespace std;

const int N = 3010;
int a[N], b[N], f[N][N];
int res, n;

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

    for ( int i = 1; i <= n; i ++ )
    {
        int maxv = 1;   //满足k从1到j-1的情况的最大值
        for ( int j = 1; j <= n; j ++ ) 
        {
            f[i][j] = f[i - 1][j];
            if ( a[i] == b[j] ) f[i][j] = max(f[i][j], maxv);
            if ( a[i] > b[j] ) maxv = max(maxv, f[i][j] + 1);
        }
    }
    for ( int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    cout << res;
    return 0;
}