#P8184. Cow Photography Order
Cow Photography Order
Cow Photography Order
Farmer John is arranging his (N) cows ((1\le N\le 10^5)) for a photograph. The cows are uniquely numbered from (1) to (N). Initially, they stand in the order (a_1,a_2,\dots,a_N) from left to right. Farmer John’s goal is to rearrange them so that they appear in the order (b_1,b_2,\dots,b_N) from left to right.
In order to achieve the desired ordering, he is allowed to perform a series of modifications. In each modification, he may choose a single cow and move it any number of positions to the left.
Determine the minimum number of modifications required so that the cows will be arranged in the desired order.
Hint: Note that cows that are not moved will remain in their original relative order. Hence, if a suffix of the desired order already appears in an increasing order (with respect to the initial positions), they do not need to be moved. In particular, if we denote by (pos(x)) the position of cow (x) in the initial order, and if there exists a largest index (k) such that (pos(b_{k}) < pos(b_{k+1}) < \cdots < pos(b_{N})), then the answer is (N - (N-k+1)).
inputFormat
The input consists of three lines:
- The first line contains a single integer (N), the number of cows.
- The second line contains (N) space-separated integers (a_1, a_2, \dots, a_N), representing the initial order of the cows.
- The third line contains (N) space-separated integers (b_1, b_2, \dots, b_N), representing the desired order of the cows.
outputFormat
Output a single integer: the minimum number of modifications required so that the cows are arranged in the desired order.
sample
5
3 1 2 4 5
1 2 3 4 5
2