Proficient.
Put your skills to the test.

Problem summary

Cut the first of two permutations into the fewest consecutive pieces so that rearranging the pieces produces the second permutation. Pieces cannot be reversed.

Constraints

2 ≤ N ≤ 100000.

Worked example

An independently prepared example for this explanation.

5
4 3 2 5 1
1 2 5 3 4

4

Solution analysis

1. Store position[v], the position of value v in the target permutation. A boundary between adjacent original values u,v can stay uncut exactly when position[v]=position[u]+1.
2. Every boundary failing this condition must be cut, since the two neighboring squares cannot remain adjacent inside a piece. Cut precisely those boundaries. Each resulting maximal block appears consecutively in the target.
3. For 4,3,2,5,1 and target 1,2,5,3,4, only the adjacency 2 followed by 5 survives. The four pieces are [4], [3], [2,5], [1], which can be rearranged into the target order.

Why it works

Each failed adjacency forces a distinct cut, giving a lower bound of one plus their number. Cutting all such boundaries creates blocks whose adjacent elements all occur consecutively in the target; their positions therefore form contiguous disjoint target intervals. Sorting these blocks by target position reconstructs the target and achieves the lower bound.

Watch out. The answer is the number of pieces, not cuts. Target adjacency is directional because reversing pieces is forbidden.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
// Algorithm: Store position[v], the position of value v in the target permutation.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>first(n),position(n+1);
    for(int&value:first){
        cin>>value;
    }
    for(int i=0;i<n;++i){
        int value;
        cin>>value;
        position[value]=i;
    }
    int pieces=1;
    for(int i=1;i<n;++i){
        if(position[first[i]]!=position[first[i-1]]+1){
            ++pieces;
        }
    }
    cout<<pieces<<'\n';
}