Observation: Consider two cows $a_i$ and $a_j$ such that $a_i$ is to the left of $a_j$ in $a$ but to the right of $a_j$ in $b$ (for example, $a_3=3$ and $a_4=2$ in sample 2). Then Farmer John must choose cow $a_j$ at least once.

Proof: If cow $a_i$ is to the left of cow $a_j$, then any modification FJ performs that does not involve choosing cow $a_j$ preserves the relative order of cows $a_i$ and $a_j$. So if FJ never chooses cow $a_j$ then $a_i$ will still be to the left of $a_j$ at the end, contradiction.

Claim: The answer is equal to the number of cows $a_j$ in $a$ such that there exists $a_i$ such that $(a_i,a_j)$ satisfy the observation above. This will be proven later in the analysis.

This claim leads to a solution in $O(N^3)$. Go through all pairs of cows $(a_i,a_j)$ such that $i<j$ and check if cow $j$ must be moved according to the observation above. Then print the total number of cows that need to be moved.

My code:

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
need_to_move = [0]*N
 
def pos_in_B(x):
	for i in range(N):
		if B[i] == x:
			return i
 
for i in range(N):
	for j in range(i+1,N):
		if pos_in_B(A[i]) > pos_in_B(A[j]):
			need_to_move[j] = 1
 
print(sum(need_to_move))

One simplification we can make is by relabeling the cows so that cow $b_i$ becomes cow $i$. For example, we may rephrase the second sample case,

a = [5 1 3 2 4] -> a = [2 4 5 3 1]
b = [4 5 2 1 3] -> b = [1 2 3 4 5]

Then we may rephrase the problem as sorting the cows in increasing order of label. Now we can rephrase the observation as checking for each $j$, whether there exists $i<j$ such that $a_i>a_j$. Here is a solution running in $O(N^2)$:

My code:

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

pos_in_B = [0]*(N+1)
for i in range(N):
	pos_in_B[B[i]] = i+1

A = [pos_in_B[v] for v in A]
# now assume B=1...N

ans = 0
for j in range(N):
	need_to_move_j = False
	for i in range(j):
		if A[i] > A[j]:
			need_to_move_j = True
	if need_to_move_j:
		ans += 1
print(ans)

We can optimize this to $O(N)$ time by maintaining the quantity $\texttt{max_so_far}=\max(a_1,a_2,\ldots,a_{j-1})$. If $\texttt{max_so_far}>a_j$, then we should to move cow $a_j$ to the left while there is a cow with greater label than $a_j$ to the left of cow $a_j$. Otherwise, cow $a_j$ has greater label than all cows to the left of it, and we set $\texttt{max_so_far}=a_j$. In either case, the first $j$ cows in $a$ will be in the same order as they are in $b$. It follows that when $j=N$, $a=b$.

My code:

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

pos_in_B = [0]*(N+1)
for i in range(N):
	pos_in_B[B[i]] = i+1

A = [pos_in_B[v] for v in A]
# now assume B=1...N

max_so_far = 0
ans = 0
 
for a in A:
	if a > max_so_far:
		max_so_far = a
	else:  # max_so_far remains the same
		ans += 1
 
print(ans)

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class MovingLeft {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        StringTokenizer tokenizerA = new StringTokenizer(in.readLine());
        StringTokenizer tokenizerB = new StringTokenizer(in.readLine());
        int[] a = new int[n];
        int[] b = new int[n];
        for (int j = 0; j < n; j++) {
            a[j] = Integer.parseInt(tokenizerA.nextToken());
            b[j] = Integer.parseInt(tokenizerB.nextToken());
        }
        int answer = 0;
        boolean[] moved = new boolean[n + 1];
        int k = 0;
        for (int j = 0; j < n; j++) {
            while (moved[a[k]]) {
                k++;
            }
            if (b[j] == a[k]) {
                k++;
            } else {
                answer++;
                moved[b[j]] = true;
            }
        }
        System.out.println(answer);
    }
}