UVA 12747 / LCS-LIS

/***
 created: 2022-07-25-23.18.54
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll n,m,i,j,k,l;

        cin>>n;

        ll a[n+4],b[n+4];

        for(i=1;i<=n;i++)
        {
            cin>>m;
            a[m]=i;
        }
        for(i=1;i<=n;i++)
        {
            cin>>m;
            b[i]=a[m];
        }
        vector<ll>x;
        x.push_back(b[1]);
        for(i=2;i<=n;i++)
        {
            k=upper_bound(x.begin(),x.end(),b[i])-x.begin();
            if(k==x.size())
            {
                x.push_back(b[i]);
            }
            else x[k]=b[i];
        }
        cout<<"Case "<<cs<<": "<<(n-x.size())*2<<nl;
    }
    get_lost_idiot;
}